UVA 3026：Period （KMP求周期串）

数据结构

题面链接

• 题意

给你一个长度为 n 的字符串 s，判断这个字符串的周期串长度（大于1的周期串），并输出之间存在多少个周期
（2 ≤ N ≤ 1000000）

• 样例

Sample Input
3 //字符串长度
aaa //这个串
12
aabaabaabaab
0

Sample Output
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4

• 分析

对字符串进行next数组的处理
字符串下标从0开始
循环字符串 当 （i+1）%（i-next[i]）==0时表示从0到i位置是一个周期串
周期串个数 num=(i+1)/(i-Next[i]);

• 代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e6+6;
int Next[maxn];
void getnext(char s[])//next数组的处理
{
    int l=strlen(s);
    Next[0]=-1;
    int j=-1;
    for(int i=1;i<l;i++)
    {
        while(j>=0&&s[j+1]!=s[i])
            j=Next[j];
        if(s[j+1]==s[i])
            j++;
        Next[i]=j;
    }
}
char s[maxn];
int main()
{
    int n,i,num,t=0;
    while(scanf("%d",&n)&&n!=0)
    {
        memset(Next,0,sizeof(Next));
        scanf("%s",s);
        getnext(s);
        printf("Test case #%d\n",++t);
        for(i=1;i<n;i++)
        {
            if((i+1)%(i-Next[i])==0&&Next[i]!=-1)
            {
                num=(i+1)/(i-Next[i]);
                printf("%d %d\n",i+1,num);
            }
        }
        puts("");
    }
    return 0;
}