(BOJ) 4354 문자열 제곱

문제: https://www.acmicpc.net/problem/4354

 

 

문제풀이:

1. KMP의 fail 배열을 채움

2. 입력 들어온 문자열의 길이를 len이라고 할 때, 

 

#1

ababab

-> len=6

-> fail[len-1] = 4

-> len-fail[len-1] = 2         // 2개가 

-> len/(len-fail[len-1]) =3    // 3번 반복됨

 

#2

abcabcabc

-> len=9

-> fail[len-1]=6

-> len-fail[len-1] = 3         // 3개가 

-> len/(len-fail[len-1]) =3    // 3번 반복됨

 

∴ 즉 정답은 len/(len-fail[len-1])임을 알 수 있다.

 

 

BUT!

abcabcab같은 경우 fail[len-1]함수가 1보다 크지만, 반복되는 문자열로 딱 나눠지지 않는다

-> len%(len-fail[len-1]) != 0 

-> 이런 문자열에서 답은 항상 1

 

 

 

소스 코드:

int fail[1000001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	while (1) {
		string s;
		cin >> s;
		if (s == ".") break;
		memset(fail, 0, sizeof(fail));
		int len = s.size();
		for (int i = 1, j = 0; i < len; i++) {
			while (j > 0 && s[i] != s[j]) j = fail[j - 1];
			if (s[i] == s[j]) fail[i] = ++j;
		}
		int t = fail[len - 1];
		if (len % (len - t)) cout << "1\n";
		else cout << len / (len - t) << '\n';
	}
	return 0;
}