Southeastern Europe 2004

当前位置 : 首页 > 网页制作 > CSS > Southeastern Europe 2004

Southeastern Europe 2004

来源: 作者: 时间:2016-01-28 09:27
PeriodKMP 啊 错位部分是一个循环节啊 includeiostream includestring includestdio h using namespace std; string s; int n; int next[1000010]; void getnext(
Period
KMP 啊 错位部分是一个循环节啊
 
#include<iostream>  
#include<string>  
#include<stdio.h>  
using namespace std;  
string s;  
int n;  
int next[1000010];  
  
  
void getnext()  
{  
    int min =1;  
    int x;  
    int k=-1,j=0;  
    next[0]=-1;  
    while(j<n)  
    {  
        if(k==-1||s[j]==s[k])  
        {  
            j++;  
            k++;  
            next[j]=k;  
            if(j%(j-k)==0&&j/(j-k)>1)  
            printf("%d %d\n",j,j/(j-k));  
        }  
        else  
            k=next[k];    
    }  
}  
int main()  
{  
    int cnt =1;  
    while(cin>>n,n)  
    {  
        cin>>s;  
        printf("Test case #%d\n",cnt++);  
        getnext();  
        puts("");  
    }  
    return 0;  
}  

 

 
 
Tag:

相关文章

网友评论

<