BOJ)4354 문자열 제곱

문제: icpc.me/4354

문자열 A가 주어질 때, A를 서로 같은 부분 문자열 N개로 쪼갤 수있을 때 N의 최댓값을 출력하는 문제다.

우리는 문자열이 N개의 부분 문자열로 쪼개질 때 규칙성을 찾아보면 

KMP에서의 pi배열의 pi[a.length()-1]=(n-1/n)*a.length()를 만족한다는 걸 알 수 있다.

이를 이용하여 최대 N을 계산해주면 된다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
string a;
vector<int> pi;
void getpi(){
    pi.clear();
    pi.resize(a.length());
    int j = 0;
    for (int i = 1; i < a.length(); i++){
        while (j > 0 && a[i] != a[j])
            j = pi[j - 1];
        if (a[i] == a[j])
            pi[i] = ++j;
    }
}
int main() {
    while (1) {
        cin >> a;
        if (a == ".")
            break;
        getpi();
        for (int i = a.length(); i > 0; i--) {
            if (pi[a.length() - 1] == (double)((double)(i - 1) / i)*(double)a.length()) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}