POJ 2752 KMP中next数组的理解

感觉这里讲的挺好的。http://cavenkaka.iteye.com/blog/1569062

就是不断递归next数组。长度不断减小。

题意:给你一个串,如果这个串存在一个长度为n的前缀串,和长度为n的后缀串,并且这两个串相等,则输出他们的长度n。求出所有的长度n。

思路:KMP中的get_next()。对前缀函数next[]又有了进一步的理解,str[1]~~str[next[len]]中的内容一定能与str[1+len-next[len]]~~str[len]匹配(图1)。然后呢我们循环地利用next,由于next的性质,即在图2中若左红串与左绿串匹配,则左红串比与右绿串匹配,因为图1的左红串与右红串是完全相等的。可以保证,每一次得出的字串都能匹配到最后一个字母,也就是得到一个前缀等于后缀。只不过这个字符串的长度在不断地减小罢了。

POJ 2752 KMP中next数组的理解

但是呢。。代码还是用的自己的。因为还是看不太懂别的求next数组的方法。

自己模拟了一下。我的代码应该是没有优化的。

 #include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std; int next[];
char str[];
int ans[]; void getNext(char str[]) {
int len=strlen(str+);
next[] = ;
for (int k=, q=; q<=len; ++q) {
while(k> && str[k+] != str[q])
k=next[k];
if (str[k+] == str[q])
k++;
next[q] = k;
}
} int main()
{
while(scanf("%s",str+)!= EOF)
{
int len = strlen(str+);
getNext(str);
ans[] = len;
int n = , i = len;
while(next[i]> )
{
n++;
ans[n] = next[i];
i = next[i];
}
for(i = n; i >= ; i--)
printf("%d ", ans[i]);
printf("\n");
}
return ;
}
上一篇:sql 注入命令大全


下一篇:CF939D Love Rescue 并查集