POJ - 1961 Period(KMP)

分手后的思念是犯贱 2022-06-05 08:48 188阅读 0赞

[点我看题][Link 1]

题意：找一个字符串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;
    }

[Link 1]: http://poj.org/problem?id=1961