0

以下是 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 是空字符串，它是每个字符串的后缀。

我对上述代码的问题

  1. 为什么作者在第 4 行选择 k 作为 min(m + 1, q+2)？

  2. 在下面的解释文本中，作者提到“代码以 k 的最大可能值开始，即 min(m, q+1)。” 哪个与上面第 4 行的伪代码不匹配？

要求在回答上述问题时用简单的例子和​​psudoe代码的步骤来解释。

4

0 回答 0