关于kmp算法和二叉链表的疑问

主题：关于kmp算法和二叉链表的疑问

aigle [专家分：0] 发布于 2006-04-03 17:06:00

在kmp算法中的next函数值的求法是怎样的啊？看了书感觉还是有些不理解。
还有在二叉链表中，讲有N个结点就有N＋1个空链域，有些不理解，希望大家能帮小弟解决一下困惑，谢谢！

沙发

narsh [专家分：790] 发布于 2006-04-03 17:45:00

0：next函数其实就是匹配串和自己的比较
1：因为是二叉链表，所以每个节点有两个链域，N个节点一共有2*N个链域
2：没有一个链域是指向根节点的，两外N-1个节点都有一个链域指向他们，也就是说有N-1个链域是非空的
3：所以空链域的个数为2*N-（N-1）=N+1

板凳

euc [专家分：4310] 发布于 2006-04-03 20:09:00

narsh说的好。一个错字：‘两外’-》‘另外’。
感觉这种证明不太直观，应该有正面的证明吧。

3 楼

aigle [专家分：0] 发布于 2006-04-03 21:49:00

对，next函数值是匹配串与自己的比较，但它的值的具体求法能具体讲一下吗？

4 楼

高焱 [专家分：200] 发布于 2006-04-04 15:51:00

我刚学完这一章，告诉你个技巧，抱着一定能看会的心态，看三遍就会了，我的理解是，当主串i与子串j不相匹配时，它会寻找next[j],假如还不匹配，找next[next[j]];直道找到匹配或j==1为止，它的实质是找与i不匹配的所有子串的最大值，并且子串的尾字母还必须和i相配。

您尚未登录，请登录后再回复。点此登录或注册