lessons/参考实现/04-KMP与Manacher/POJ-2406.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (cin >> s && s != ".") {
        int n = static_cast<int>(s.size());
        vector<int> pi(n);
        for (int i = 1; i < n; ++i) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) ++j;
            pi[i] = j;
        }
        int period = n - pi[n - 1];
        cout << (n % period == 0 ? n / period : 1) << '\n';
    }
}