[FOJ1901 Period II]拓展KMP算法

【题目大意】
给出一个串，让你求出所有满足S[1..n-k+1]=S[k..n]的k-1的值。
【算法分析】
一看到题目。。。这不就是拓展KMP的数组直接判断么。。。
于是直接写了拓展KMP。
虽然KMP也可以。
这个当做是我的拓展KMP例题好了。
【CODE】
#include #include #include #define max(x,y) ((x)>(y)?(x):(y))
const int N=1000005;
int n,ans;
int b[N],ansl[N];
char S[N];

void exkmp(){
int i,j,k,a,p;
b[1]=n;
for (i=2;i<=n && S[i]==S[i-1];i++);
i–;
b[2]=i-2+1;
p=i;
a=2;

for (i=3;i<=n;i++)
if (b[i-a+1]+i-1 b[i]=b[i-a+1];
else{
k=max(p+1-i,0);
while (i+k<=n && S[i+k]==S[k+1]) k++;
b[i]=k;
a=i;
p=i+b[i]-1;
}

ans=0;
for (i=2;i<=n;i++)
if (b[i]==n-i+1) ansl[++ans]=i-1;
ansl[++ans]=n;
printf("%dn",ans);
for (i=1;i<=ans;i++){
printf("%d",ansl[i]);
if (i==ans) printf("n");
else printf(" ");
}
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
scanf("%s",S+1);
n=strlen(S+1);
exkmp();
}
}