string - 坚持 Apostolico-Crochemore 算法

Question

我正在尝试理解 Apostolico-Crochemore 算法。

我找到的唯一英文描述是http://www-igm.univ-mlv.fr/~lecroq/string/node12.html#SECTION00120 , 但我坚持描述的第二行

x is a power of a single character

这是什么意思？

m 在这种情况下是模式的长度，c 是使用的字母表中的一个字符。我无法理解 x == c^m。

然后是 (x=(a^l)bu for a, b in Sigma，Sigma 中的 u 和 a neq b 也使用了我无法理解的 ^ 操作。

Answer 1

字符串算法有时用正式语言的行话来描述，其中字符串的连接(连接)被写成乘法:x * y，通常只写成 xy , 表示“字符串 x 后跟字符串 y”。所以 x^n(即“将字符串 x 提高到 n 次方”)自然意味着“n字符串 x 的副本，连接在一起”。

这主要只是一种符号设备，尽管(普通实数的)乘法和字符串连接确实共享一些抽象的数学属性。例如。它们都是关联的:(xy)z = x(yz)，无论我们是在谈论乘法还是连接字符串。 (OTOH，一般来说，xy = yx 对于实数而不是字符串。但是矩阵乘法也不是可交换的。)