POJ 2752 KMPnext的应用 - c++编程基础

题意：求字符串的前缀和后缀相同的所有长度。

其实只要理解了next数组就行了，s[1~next[j]] = s[1+j-next[j] ~ j]，所以，求完最长的长度，也就是前缀是s[1~next[len]]，然后直接递归把这个前缀当做字串去求最长合法串就行了。

描述比较渣，在纸上画出字符串和next数组，就知道了。

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        poj2752.cpp 
*  Create Date: 2013-11-28 14:17:21 
*  Descripton:  kmp  
*/  
  
#include   
#include   
  
const int MAXN = 4e5 + 1;  
  
char s[MAXN];  
int f[MAXN];  
  
void getVal(char *P, int l) {  
    int i = 0, j = -1;  
    f[0] = -1;  
    while (i < l) {  
        if (j == -1 || P[i] == P[j]) {  
            i++; j++;  
            f[i] = j;  
        } else j = f[j];  
    }  
}  
  
void solve(int j) {  
    if (f[j] < 0) return;  
    solve(f[j]);  
    printf("%d ", j);  
}  
  
int main() {  
    while (~scanf("%s", s)) {  
        int len = strlen(s);  
        getVal(s, len);  
        solve(len);  
        puts("");  
    }  
    return 0;  
}