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;
}