<>

<>

题目大意：

 给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。从小到大依次输出这些子串的长度。即输出该字符串所有前缀后缀相等的子串的长度。

解题分析：

    如左图，假设黑色线来代表字符串str，其长度是len，红色线的长度代表next[len]，根据next数组定义易得前缀的next[len]长度的子串和后缀next[len]长度的子串完全相同（也就是两条线所对应的位置）。我们再求出next[len]位置处的next值，也就是图中蓝线对应的长度。同样可以得到两个蓝线对应的子串肯定完全相同，又由于第二段蓝线属于左侧红线的后缀，所以又能得到它肯定也是整个字符串的后缀。

    所以对于这道题，求出len处的next值，并递归的向下求出所有的next值，得到的就是答案。

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int M =4e5+7;char s[M];int nxt[M];void getnext(){    int i=0,j=-1;    nxt[0]=-1;    while(s[i]){        if(j==-1||s[i]==s[j]){            nxt[++i]=++j;        }        else j=nxt[j];    }}int main(){    while(gets(s)){        getnext();        int len=strlen(s);        int res=len;        int cnt=0,output[M];        while(nxt[res]>0){     //按上面分析的方式转移             output[++cnt]=nxt[res];            res=nxt[res];        }        sort(output+1,output+1+cnt);        for(int i=1;i<=cnt;i++){            printf("%d ",output[i]);        }        printf("%d\n",len);    }        return 0;}
       
      
     

 

2018-08-06