poj_2752 kmp

题目大意

    给定字符串S，求出S的所有可能相同前后缀的长度。比如： 
"alala"的前缀分别为{"a", "al", "ala", "alal", "alala"}, 后缀分别为{"a", "la", "ala", "lala", "alala"}. 其中有{"a", "ala", "alala"}是相同的，即输入1,3,5.

题目分析

    首先，根据题目的意思，一个串本身就是它的相同前后缀。然后，考虑长度稍小一点的前后缀： 
    有了kmp算法的next数组（保存某段子串的相同前后缀的最大长度，不包括自身），可以从最长的相同前后缀开始考虑，对于串S，根据next[strlen(S)-1]得到的最长相同前后缀为S1,则再根据next[strlen(S1)-1]得到的S1的最长相同前后缀S2肯定也为S的相同前后缀。（通过画图可以很容易的证明）。 
    这样，通过不断的向前查找next数组，得到一系列的相同前后缀。下面证明这些前后缀包含了所有的相同前后缀： 
        由于我们得到的是一系列最长相同前后缀，假设有一个相同的前后缀Sk不属于这些通过next递推得到的前后缀集合，那么len(Sk)必定小于len(S1)，且Sk必定为S1的子串（通过画图很容易看出来）；此时若Sk是S1的最长前后缀，则与前提Sk不为某一子串的最长前后缀矛盾，那么Sk不是S1的最长前后缀，则可以退出len(Sk)必定小于S2，且Sk必定为S2的相同前后缀..... 数学归纳递推下去，可以知道Sk要么为某个Si的最长前后缀，要么len(Sk) = 0. 这样可以证明这些通过next数组递推得到的前后缀包含了所有的相同前后缀

实现(c++)

#define _CRT_SECURE_NO_WARNINGS
#define MAX_WORD_LEN  400005
#include<stdio.h>
#include<string.h>
int gNext[MAX_WORD_LEN];
char gWord[MAX_WORD_LEN];
int gLength[MAX_WORD_LEN];
void GenerateNext(const char* sub_str, int* next, int len){
	next[0] = 0;								//next[i]表示sub_str[0, i]中最长相同前后缀的长度
	for (int i = 1; i < len; i++){
		int j = next[i - 1];
		while (sub_str[j] != sub_str[i]){		//不断回溯，每次利用next数组来确定下一个需要判断的位置
			if (j == 0){
				j = -1;
				break;
			}
			j = next[j - 1];
		}
		if (j < 0)
			next[i] = 0;
		else
			next[i] = j + 1;
	}
}
int GetPreSuffix(int* next, int len){
	int  i = len;
	int count = 0;
	while (next[i-1]){
		gLength[count++] = i;
		i = next[i-1];
	}
	gLength[count++] = i;
	return count;
}
int main(){
	while(scanf("%s", gWord)!= EOF){
		int len = strlen(gWord);
		GenerateNext(gWord, gNext, len);
		int count = GetPreSuffix(gNext, len);
		for (int i = count - 1; i >= 0; i --)
			printf("%d ", gLength[i]);
		printf("
");
	}
	return 0;
}