回 帖 发 新 帖 刷新版面

主题:[讨论]关于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++写程序该用哪中方法?

回复列表 (共1个回复)

沙发

第一种是0下标开始
第二种是1下标开始

至于用哪种不是KMP算法的关键问题,取决于你所处的环境
例如在C中下标从0开始 在Pascal中下标从1开始

next(2)和next(4)都是初等的运用KMP算法,其实是MP算法,Knuth后来又进一步完善,等到next(1) next(3) ,就是求得初次的next值后,在与所期望next值位置的字符做比较,白话说就是next的更彻底一点

next5像是失配时预期的匹配前缀的长度,还需要计算一下移动位数

我来回复

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