FZU - 1901 Period II(kmp所有循环节)

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

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

题意:求出一个字符串的所有可能循环节的长度

思路:kmp的运用，题目的意思不是很清楚 j=next[j] 就是次大的匹配个数

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

#define ll long long int

using namespace std;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int moth[]={,,,,,,,,,,,,};

int dir[][]={, ,, ,-, ,,-};

int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

int nextt[];

void getnext(string s){

    nextt[]=; int len=s.length();

    for(int i=,j=;i<=len;i++){

        while(j>&&s[i-]!=s[j]) j=nextt[j];

        if(s[i-]==s[j]) j++;

        nextt[i]=j;

    }

}

int main(){

    ios::sync_with_stdio(false);

    int t;

    cin>>t;

    int w=;

    while(t--){

        string s;

        cin>>s;

        getnext(s);

        int len=s.length();

        queue<int> q;

        int j=nextt[len];

        while(j>){

            q.push(j);

            j=nextt[j];

        }

        q.push();

        bool f=;

        cout<<"Case #"<<++w<<": "<<q.size()<<endl;

        while(!q.empty()){

            int temp=q.front();

            q.pop();

            if(f){

                cout<<len-temp;

                f=;

            }else{

                cout<<" "<<len-temp;

            }

        }

        cout<<endl;

    }

    return ;

}

巴特西