poj_2752 Seek the Name, Seek the Fame

?

?

分析：

题目要求一个既是S的前缀又是S的后缀的子串（S本身是自己的前缀又是自己的后缀）。主要利用next数组求解。

e.g.

?

?

Out: 2 4 9 18
由于子串既是S的前缀又是后缀，所以除去字符串本身长度18外，次长的为在字符串结束符‘’处求得的next数组值9，

此时S的前缀为 ababcabab(012345678)，S的后缀为 ababcabab(9-17)。接着找第三长的既是S的前缀又是S后缀的子串。

如果找next[17]处的值8，则不满足是S后缀的要求，因为17本身的字符是被排除在外的，10-16亦是同理。

而对于9之前的子串有next[18]知既是S的前缀又是S的后缀。而next[9]的值4指明了位置在9前的子串的前后缀长度为4，

而该子串包含在S的前缀中，所以该子串的后缀也包含在S的前缀中，而S的前缀又是S的后缀，所以该子串的后缀也是S的后缀。

依次往前直到满足条件的子串长度为0为止。

?

代码：

?

//seek the name,seek the fame
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define MAXN 400004 int plen; int next[MAXN]; //MAXN模式串长度 char pat[MAXN]; void getNext() { int j=0, k=-1; next[0]=-1; while(j
      
       -1 && pat[j]!=pat[k]) k=next[k]; next[++j]=++k; } } void show(int n) { if(next[n]>0){ show(next[n]); printf(%d ,next[n]); } } int main() { //freopen(in.txt,r,stdin); while(cin>>pat){ plen=strlen(pat); getNext(); show(plen); cout<
       
        
?