FZU1901 Period II —— KMP next数组

题目链接：https://vjudge.net/problem/FZU-1901

 Problem 1901 Period II

Accept: 575    Submit: 1495
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

For each prefix with length P of a given string S,if

S[i]=S[i+P] for i in [0..SIZE(S)-p-1],

then the prefix is a “period” of S. We want to all the periodic prefixs.

 Input

Input contains multiple cases.

The first line contains an integer T representing the number of cases. Then following T cases.

Each test case contains a string S (1 <= SIZE(S) <= 1000000),represents the title.S consists of lowercase ,uppercase letter.

 Output

For each test case, first output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of periodic prefixs.Then output the lengths of the periodic prefixs in ascending order.

 Sample Input

4 ooo acmacmacmacmacma fzufzufzuf stostootssto

 Sample Output

Case #1: 3 1 2 3 Case #2: 6 3 6 9 12 15 16 Case #3: 4 3 6 9 10 Case #4: 2 9 12

 Source

FOJ有奖月赛-2010年05月

题解：

求出该字符串的所有循环节。

求出字符串的next数组。可知len-next[len]就是字符串的最小循环节，然后next数组回退，len-next[next[len]]就是第二小循环节……

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
const double eps = 1e-6;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 1e6+10;

char x[MAXN];
int Next[MAXN];

void get_next(char x[], int m)
{
    int i, j;
    j = Next[0] = -1;
    i = 0;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j]) j = Next[j];
        Next[++i] = ++j;
    }
}

int ans[MAXN];
int main()
{
    int T, kase = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", x);
        int len = strlen(x);
        get_next(x, len);

        int cnt = 0;
        for(int k = Next[len]; k!=-1; k = Next[k])
            ans[++cnt] = len-k;

        printf("Case #%d: %d
", ++kase, cnt);
        for(int i = 1; i<=cnt; i++)
        {
            printf("%d", ans[i]);
            if(i!=cnt) printf(" ");
        }
        printf("
");
    }
}