某一个网页打不开是什么原因_运营主要做什么工作_企业网络推广方案_百度统计app下载

在《数据结构：利用递推式计算next表》一文中，阐述了一种计算 next 表的方法。下面再介绍另外一种方法。

2. 通过 PM 值计算

由于“在 t[0, j) 中长度为 k 的真前缀，应与长度为 k 的真后缀完全匹配”，且“k 取最大值”，所以，对于模式串 t ，可以通过计算它所有子串的真前缀和真后缀的交集，并且找出交集中最长字符串的长度值，这个值称为 PM 值（Partial Match，部分匹配值）。

例如模式串 t = 'abcac' ，按照这种方法可得：

子串	真前缀集合	真后缀集合	交集中最长	PM值
'a'	空集	空集	空集	0
'ab'	{'a'}	{'b'}	空集	0
'abc'	{'a', 'ab'}	{'c', 'bc'}	空集	0
'abca'	{'a', 'ab', 'abc'}	{'a', 'ca', 'bca'}	'a'	1
'abcac'	{'a', 'ab', 'abc', 'abca'}	{'c', 'ac', 'cac', 'bcac'}	空集	0

将 t = 'abcac' 对应的 PM 值转化为下面的表格，即 PM 表。

index	0	1	2	3	4
t[]	a	b	c	a	c
PM	0	0	0	1	0

假设有主串 s = 'ababcabcacbab' ，下面用 PM 表进行字符串匹配。

• 第一趟匹配，如图 6.3.7 中所示的位置匹配失败，即 s[2] 与 t[2] 不匹配，此时 j = 2。

图 6.3.7 第一趟匹配

从图中观察可知，模式串 t 应向右移动的 2 个字符，结合图 7.4.4，可知模式串向右移动的位数。

$$\begin{array}{rl}\text{move}& =j-k(\text{即：已经匹配字符数 - 已经匹配字符的PM值})\\ & =j-\text{PM}[j-1]\end{array}$$
对于图 6.3.7 所示情况，即为：j - PM[j-1=1] = 2 - 0 = 2 。从而得到图 6.3.8 的结果，并继续第二趟匹配。

• 第二趟匹配（如图 6.3.8），在 j = 4 处匹配失败，根据上面的计算方法，得到再次向右移动的字符数：j - PM[j-1=3] = 4 - 1 = 3 ，即再次向右移动 3 个字符，并进入下一轮匹配。

  

  图 6.3.8 第二趟匹配
  

  如此反复，直到匹配成功（图 6.3.8 所示的下一趟即匹配成功）。

若令 $\text{PM}[j-1]=\text{next}[j]$ ，即将 PM 值整体向右移动一位，得到如下表所示的结果：

index	0	1	2	3	4
t[]	a	b	c	a	c
PM	0	0	0	1	0
next[]		0	0	0	1

• PM 值的最后一个值“溢出”。由上述计算公式可知，使用的 PM 值总是到 PM[j-1] ，所以模式串 t 的最后一个元素的 PM 值在计算中没有价值，可以舍去。
• 上表中，next[0] 的值目前空缺，于是将上节课所设置的值填充于此，令 next[0] = -1 。于是得到如下所示的 next 表：

index	0	1	2	3	4
t[]	a	b	c	a	c
PM	0	0	0	1	0
next[]	-1	0	0	0	1

例 6.3.2： 已知串 t = '000010' ，计算 next 表（或称：next 数组值）。

【解】

如下所示，计算 PM 值。

子串	真前缀集合	真后缀集合	交集中最长	PM值
'0'	空集	空集	空集	0
'00'	{'0'}	{'0'}	'0'	1
'000'	{'0', '00'}	{'0', '00'}	'00'	2
'0000'	{'0', '00', '000'}	{'0', '00', '000'}	'000'	3
'00001'	{'0', '00', '000', '0000'}	{'1', '01', '001', '0001'}	空集	0
'000010'	{'0', '00', '000', '0000', '00001'}	{'0', '10', '010', '0010', '00010'}	'0'	1

所以，t = '000010' 对应的 PM 值是 012301 ，相应地得到下面的 PM 表，并将 PM 值向右移动一个位置，得到 next 数组值，同时令 next[0] = -1。

Index	0	1	2	3	4	5
t[]	0	0	0	0	1	0
PM	0	1	2	3	0	1
next[]	-1	0	1	2	3	0

此结果与【例 6.3.1】 的结果一致。

注意：以上示例中的模式串 t 的下标是从 0 开始编号，则直接将 PM 值向右移动一位即可；若模式串下标是从 1 开始编号，则需要将 next 数组值整体加 1，即如下表所示。

位序	1	2	3	4	5	6
t[]	0	0	0	0	1	0
PM	0	1	2	3	0	1
next[]	0	1	2	3	4	1

这种方式是《数据结构》教材（严蔚敏，人民邮电出版社，2015年2月第2版）中所采用的，令 next[1] = 0 。