Seek the Name, Seek the Fame（KMP之next数组应用）

参考网址：http://blog.csdn.net/niushuai666/article/details/6968507

题目大意：

给你一个字符串S。假如为ababcababababcabab.找出这个字符串中所有的前缀等于后缀的子串。输出它们的长度。

第一个为a，最后一个为b，所以1不行。

前两个为ab，最后二个也为ab，所以2行。

前三个为aba，后三个为bab，所以3不行。

以此类推。。找出全部

当然，全部字符串也是可以的。因为ababcababababcabab和ababcababababcabab肯定是一样的。。。。

解题思路：

这道题也是next数组的一个应用。

既然是求模式串匹配，所以要先求出模式串的next数组。这是第一步。

然后我们开始分析怎么用next数组来完成查找前缀后缀的匹配。

我们还是用上面那个字符串为例子来说明一下。

下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
模式串 a b a b c a b a b a b a b c a b a b
next[i] -1 0 0 1 2 0 1 2 3 4 3 4 3 4 5 6 7 8 9

1）当i = len时，next[len] = next[18] = 9，说明整个字符串前9个字符和后9个字符相同，所以9是满足要求的。

2）next[9] = 4，说明在0-8中前4个字符和后4个字符相同。因为由1）得前9个字符和后9个字符相同，所以，S串的0-3等于5-8，而0-3又等于9-12,5-8又等于14-17，所以结果是0-3等于14-17，即4也是满足题意的。（其实如果是出现了next为0 的也就是失配的也可以这么理解，出现0也是通过这种传递的方式来确认已经前后不能同时满足了）

3）next[4]=2，同2，我们可以得到2也是满足题意的。

4）next[2]=0，表明没有相同的前缀和后缀了，这时，就已经找到了这个S串的所有前缀和后缀。

5）结果就是2,4,9,18.

所以，我们可以推得这样的结论：凡是next[i]！=0的，都是模式串的前缀和后缀相同的字符数。

这也是getnext函数的一个重要应用，多理解理解就可以了。

这道题的代码量很简单，过程也不复杂，但是想要一下子就能想到这个思路，在我愚笨的智商看来好像还真的不简单，还是认真的想想吧...

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define N 400010

char str[N];
int next[N], ans[N];
int len;

void getnext()
{
	int i = 0, j = -1;
	next[0] = -1;
	while(i != len){
		if(j == -1 || str[i] == str[j])
			next[++i] = ++j;
		else
			j = next[j];
	}
}
int main()
{
	while(scanf("%s", str) != EOF)
	{
		int j = 0;
		len = strlen(str);
		getnext();
		for(int i = len; next[i] != -1; )//注意：由于next未经调整过的为下一个下标所对应的next值为当前的真正next值，因此
		                                    //这样是从len开始的 
		{
			ans[j++] = i;
			i = next[i];
		}
		for(int i = j - 1; i >= 0; --i)
			printf("%d ", ans[i]);
		printf("
");
	}
	return 0;
}

Seek the Name, Seek the Fame（KMP之next数组应用）

相关推荐