[BOJ 4354] 문자열 제곱

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

 

풀이 : 

 

KMP의 Fail 함수를 이용해서 해결하는 문제입니다.

abababab 라는 문자열이 있다고 가정해봅시다.

문자열의 길이는 len이라고 표현 하겠습니다.

이 문자열은 ab가 4번 반복되는 문자열입니다.

이 문자열의 Fail 값을 계산한다면

 

abababab

   abababab

 

00123456 이 나옵니다.

이러한 사실에서 우리가 알 수 있는 사실은

반복되는 횟수가 1이 아닌 문자열은 무조건 반복되는 기준이 있는 문자열이기 때문에

최대로 반복되는 문자열을 처음 지나는 순간 그 다음은 Fail 값이 계속 Fail[n] = Fail[n-1] + 1의 형태로 흘러가게 됩니다.

다시 abababab의 Fail값을본다면 최대로 반복되는 ab를 처음 지나는 순간부터 Fail 값이 위와 같은 형태로 증가하게 된다는 사실을 알 수 있습니다.

위와 같은 사실에 비추어 볼때 최대로 반복되는 부분문자열의 길이는 len - Fail[len - 1] 만큼 나오게 된다는 사실을 알 수 있습니다. 

또 반복되는 횟수가 1인 문자열은 len이 len - Fail[len - 1]로 나누어 떨어지지 않는다는 사실 또한 쉽게 알 수 있습니다. 

따라서 len % (len - Fail[len -1]) 가 0이면 len / (len - Fail[len - 1]) , 0이 아니면 1이 됩니다.

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
string S;
int len, fail[1000001];
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> S) {
        if (S[0] == '.')break;
        len = S.size();
        for (int i = 0; i < len; i++)fail[i] = 0;
        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 tmp = fail[len - 1];
        if (len % (len - tmp))cout << "1\n";
        else cout << len / (len - tmp) << '\n';
    }
}