Codeforces #189 Div1 D. Have You Ever Heard About the Word?

あれ？
http://codeforces.com/contest/319/problem/D

問題

文字列Sが与えられる。
もし文字列中に同じ単語の繰り返しがあった場合、最短かつ最左の繰り返しを選択し、繰り返し分を削除して１回分のみ残す。
Sは最終的にどのような文字列になるか。

解法

文字列長があまり長くないため、愚直に検索しても間に合ってしまう。
O(N^2)だけどこれでいいのか？

高速な解法をしてる人はハッシュを取ったりしてるみたいね。

int L;
char S[50001];

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>S;
	bool up=true;
	while(up) {
		L=strlen(S);
		up=false;
		
		for(l=1;l<=L/2;l++) {
			y=0;
			FOR(x,L-l+1) {
				y++;
				if(S[x]!=S[x+l]) y=0;
				if(y>=l) {
					x-=(l-1);
					break;
				}
			}
			
			if(y<l) continue;
			
			up=true;
			strcpy(S+x,S+x+l);
			break;
		}
	}
	cout << S << endl;
	
}

まとめ

サイズ設定１ケタ間違えたりしてないかな…？