ACPC2015Day3 F / AOJ 2763 - Miko Mi String

問題はこちら。

入力文字列Sについて、長さをn、最小周期をpとします。
さらに、q=p*floor(n/(3*p)+1)とおきます。
このようにすると、
2*q<nであるときかつそのときに限り、題意を満たす文字列A,Bが存在し、さらに求めるべきABの長さはqとなる
ということが容易に証明できます。

以上の考察を基にコードを書くと次のようになります。

#include <stdio.h>
#include <string.h>

char s[1000010];
int mp[1000010];

int main(){
	int i, n, t, p, q = 0;

	fgets(s, sizeof(s), stdin);
	n = strlen(s) - 1;

	mp[0] = -1;
	t = -1;
	for(i = 0; i < n; ++i){
		while(t >= 0 && s[t] != s[i]){
			t = mp[t];
		}
		mp[i + 1] = ++t;
	}
	
	p = n - mp[n];
	q = p * (n / (3 * p) + 1);
	if(q * 2 >= n){
		q = 0;
	}

	if(q != 0){
		printf("Love %.*s!\n", q, s);
	}
	else{
		puts("mitomerarenaiWA");
	}

	return 0;
}

さらに頑張ると、次の162バイトのコードになります。

char s[1<<20];m[1<<20],n,t;main(){for(gets(s);s[n];m[++n]=--t)for(;t&&s[~t]-s[n];t=m[~t]);t-=~n;n=!printf(t*2<n?"Love %.*s!\n":"mitomerarenaiWA\n",t*=n/3/t+1,s);}