POJ 2406

求NEXT[]数组

用next数组求字符串的周期

若周期大于1：next[l]会回到上一个周期的最后一个元素

#include <iostream>
#include "stdio.h"
#include <string.h>
#include <cstring>
using namespace std;
#define n 1000010
int next[1000010],l;
char s[1000010];
void getNext(){
    int j,k;
    next[0]=-1;
    j=0;
    k=-1;　　　　　　　　
    while(j<l){　　　　　　　　　　　　　　　　　　//之前L用strlen（s）代替，超时了很多次
        if(k==-1||s[j]==s[k])    {
            j++;
            k++;
            next[j]=k;
        }
        else
            k=next[k];
    }
}
int main(){
    while(1){
        scanf("%s",s);
        if(!strcmp(s,".")) break;
        l=strlen(s);
        getNext();
        if(l%(l-next[l])==0)　　　　　　　　　　　　
            printf("%d ",l/(l-next[l]));　　　　　　　　　　
        else
            printf("%d ",1);
    }
    return 0;
}