题目描述

blablabla

样例

blablabla

通过kmp求最小循环节

#include <iostream>
#include <cstring>

using namespace std;
const int N = 110;
int n;
char p[N];
int ne[N];

int main() {
    while (cin >> p + 1, *(p + 1) != '.')
    {
        n = 0;
        memset(ne, 0, sizeof ne);
        for (int i = 1; ; i ++)
        {
            if (p[i] == '\0')
            {
                break;
            }
            n ++ ;
        }
        // 求next数组   n - ne[n] 即为最小循环节
        for (int i = 2, j = 0; i <= n; i ++)
        {
            while(j && p[i] != p[j + 1]) j = ne[j];
            if (p[i] == p[j + 1]) j ++;
            ne[i] = j;
        }
        if (n - ne[n] == 0) cout << 1 << endl;
        else cout << n / (n - ne[n]) << endl;
    }

    return 0;
}