POJ - 1961 Period(KMP)

点我看题

题意：找一个字符串S的前缀(包括本身)的循环节。

分析：KMP模板题，先求出前缀表，然后对于每一个前缀，假设目前是前i个字符，他们的前后缀相等最大长度为nxt[i]，那么(i-nxt[x])就可能是循环节了，那么接下来就要判断是不是循环节了，是循环节要满足两个条件，①nxt[i] != 0，即 i != len , ②个人理解是前后缀在子串中有重合，想想看如果没有重合肯定不存在循环节的， 当然有重合也不一定有循环节（fe：aabaaba长度为7的串），有重合并且循环节的长度能够被i整除才能说存在循环节，即i%len == 0，则循环节的长度为i/len,如果不理解的话，得好好琢磨前缀表了。

参考代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;
const int maxn = 1e6+10;
int n;
char S[maxn];
int nxt[maxn];

void GetNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while( i < n)
    {
        if( j == -1 || S[i] == S[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

int main()
{
    while( scanf("%d",&n) && n)
    {
        scanf("%s",S);7
        
        static int cas = 1;
        printf("Test case #%d\n",cas++);
        GetNext();
        for( int i = 1; i <= n; i++)
        {
            int len = i-nxt[i];//循环节长度
            if( i != len && i%len == 0)
                printf("%d %d\n",i,i/len);
        }
        puts("");
    }

    return 0;
}