(字符串的模式匹配4.7.19――前缀数组suffix的应用)POJ 2752 Seek the Name, Seek the Fame(求解一个字符串中前缀和后缀一样的位

 
/* 
 * poj_2752.cpp 
 * 
 *  Created on: 2013年10月29日 
 *      Author: Administrator 
 */  
  
#include   
#include   
#include   
  
using namespace std;  
  
const int maxn =  400005;  
  
int main() {  
    char str[maxn];  
  
    while (scanf("%s", str) != EOF) {  
        int len = strlen(str);  
  
        int suffix[maxn + 1];  
        int ans[maxn+1];  
  
        //应用KMP算法计算单词w的前缀函数  
        suffix[0] = -1;  
        suffix[1] = 0;  
        int cur, p = 0;  
        for (cur = 2; cur <= len; ++cur) {  
            while (p >





= 0 && str[p] != str[cur - 1]) {  
                p = suffix[p];  
            }  
  
            suffix[cur] = ++p;  
        }  
  
        //求解前缀和后缀一样的位置..  
        int i,j = 0;  
        for(i = len ; suffix[i] != -1;){//只要suffix[i]!=-1都是前缀和后缀一样的  
            ans[j++] = i;  
            i = suffix[i];  
        }  
  
        for(i = j - 1 ; i > 0 ; --i){  
            printf("%d ",ans[i]);  
        }  
  
        printf("%d\n",ans[0]);  
    }  
  
    return 0;  
}