[POJ 2752]KMP**

【题目大意】

求所有对于同一字符串的前缀和后缀相等的位置。

【算法分析】

KMP，然后一直从n一直next回去，路上的都是。

为什么呢？

首先从在n的第一次next是找最长的S[1,K]=S[n-K+1,n]

这个容易理解。

然后接下来的next是求最长的S[1,K]=S[J-K+1,J]

注意了，这个S[J-K+1,J]必然与S[n-K+1,n]相等。（可以用数学归纳法证明一下）

于是对应下一个前缀等于后缀的位置。

所以，这样一直下去就会找到所有的前缀等于后缀的位置。

【其它】1A

http://hi.baidu.com/aekdycoin/blog/item/fbe5a03233bd1648ad4b5f1c.html

紧紧跟随师傅的脚步。

【CODE】

#include #include #include

int next[500000],n,ans[500000],ansl;
char s[500000];

int main(){
    int i,j;
    while (scanf("%sn",&s[1])!=EOF){
          n=strlen(s+1);
          next[1]=0;
          j=0;
          for (i=2;i<=n;i++){
              while (j && s[j+1]!=s[i]) j=next[j];
              if (s[j+1]==s[i]) j++;
              next[i]=j;
          }
          ansl=1; ans[1]=n;
          j=n;
          while (1){
                if (next[j]==0) break;
                j=next[j];
                ans[++ansl]=j;
          }
          for (i=ansl;i>=1;i–){
              printf("%d",ans[i]);
              if (i!=1) printf(" ");
          }
          printf("n");
    }
}