poj 2406_Power Strings_KMP

发布于 2019-05-22  907 次阅读


题目大意

求字符串的长度最小的循环节的循环次数,既求最大循环次数


思路

假设S的长度为len,则S存在循环子串,当且仅当,len可以被len - next[len]整除,最短循环子串为S[len - next[len]]


#include 
#include 
#include 
using namespace std;
#define maxn 1000005
int p[maxn];
char a[maxn];
int main()
{
    while (scanf("%s", a), a[0] != '.')
    {
        int n = strlen(a);
        int j = -1;
        p[0] = -1;
        for (int i = 1; i < n; i++)
        {
            while (a[j + 1] != a[i] && j != -1) j = p[j];
            if (a[i] == a[j + 1]) j++;
            p[i] = j;
        }

        if (n % (n - p[n - 1] - 1) == 0)
            printf("%d\n", n / (n - p[n - 1] - 1));
        else printf("1\n");
    }
}
]]>