主题:[讨论]关于KMP模式匹配算法中,求next的问题??
下标 0 1 2 3 4 5 6 7 8
T a b a b c a a b c
next(1) -1 0 -1 0 2 -1 1 0 2
next(2) -1 0 0 1 2 0 1 1 2
下标 1 2 3 4 5 6 7 8 9
T a b a b c a a b c
next(3) 0 1 0 1 3 0 2 1 3
next(4) 0 1 1 2 3 1 2 2 3
下标 0 1 2 3 4 5 6 7 8
T a b a b c a a b c
next(5) 0 0 1 2 0 1 1 2 0
表中,next(1)和next(2)都定义next[0]= -1,next(1)是next(2)的改进,如:
next(1)中表示方法next[2]= -1,表示T[2]=T[0],且T[2-1] !=T[0]
next(2)中表示方法next[2]= 0,表示T[2-1] !=T[0],但并不管T[0] 和T[2]相不相等.
next(3)和next(4)都定义next[1]=0,即数组的下标从1开始而不是0..next(3)是next(4)的改进。严尉敏的数据结构C语言版即是这种方法,而且定义next[0]为字符串的长度
next(5)是我们自己教科书上,又是另一种定义方法,定义next[0]=0,当next[3]=2,起匹配的最长前缀子串为”ab”.感觉这种方法似乎不太普遍。
所以请问各位:这三中方法在应用中各有何特点?分别在什么情况下用?如果用C++写程序该用哪中方法?