以下是 CLRS 的算法简介文本。下面是使用有限状态自动机进行字符串匹配的代码片段。Trnstion 函数用于构造带有待搜索模式的状态表。
计算转移函数:以下过程根据给定模式 P [1: :m] 计算转移函数 sigma。
COMPUTE-TRANSITION-FUNCTION.
1 m = P:length
2 for q = 0 to m
3 for each character a belongs to alphabetset
4 k = min (m + 1, q + 2)
5 repeat
6 k = k - 1
7 until Pk is suffix Pqa
8 sigma(q, a) = k
9 return sigma
此过程根据方程 (32.4) 中的定义以直接方式计算 sigma(q, a)。从第 2 行和第 3 行开始的嵌套循环考虑所有状态 q 和所有字符 a,第 4-8 行将 sigma(q, a) 设置为最大的 k,使得 Pk 是后缀 Pqa。代码从 k 的最大可能值开始,即 min(m, q+1)。然后它减小 k 直到 Pk 是后缀 Pqa,这最终必须发生,因为 P0 是空字符串,它是每个字符串的后缀。
我对上述代码的问题
为什么作者在第 4 行选择 k 作为 min(m + 1, q+2)?
在下面的解释文本中,作者提到“代码以 k 的最大可能值开始,即 min(m, q+1)。” 哪个与上面第 4 行的伪代码不匹配?
要求在回答上述问题时用简单的例子和psudoe代码的步骤来解释。