FZU 1901
简单KMP
[cpp]
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
char s[1000005];
int next[1000005],flag,len;
void getnext(){
int k=1,j=0;
next[k]=0;
while(k<=len+1){
if(j==0||s[k]==s[j]){
++j,++k;
next[k]=j;
}
else
j=next[j];
}
}
int main(){
int t,T,i;
vector<int>v;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%s",&s[1]);
len=strlen(&s[1]);
getnext();
int tem=len;
v.clear();
while(next[tem+1]>1){
v.push_back(len+1-next[tem+1]);
tem=next[tem+1]-1;
}
v.push_back(len);
//sort(v.begin(),v.end());
printf("Case #%d: %d\n",t,v.size());
for(i=0;i<v.size();i++)
if(i==0)
printf("%d",v[i]);
else
printf(" %d",v[i]);
printf("\n");
}
}
补充：软件开发 , C++ ,
