字符串匹配的扩展版本算法

Question

最近在研究字符串匹配，受到启发想到了一个类似的问题。设 p 为 m 个字符的字符串，t 为 n 个字符的文本。现在的问题是通过以下方式找出 p 是否出现在 t 中:在 [0, 范围内存在 i>n-1] 这样:

p[ j ] = t [ i + j ] 对于j = 0, 1, ... ,m - 1,

其中 i + j 是计算模 n 的。例如，在正常的字符串匹配中，ABCD 不会出现在 CDEFAB 中，但是您可以看到在上面定义的问题中，ABCD 会出现在 CDEFAB 中，本例中 i = 4。

是否有任何线性时间算法来确定模式 p 是否出现在 t 中？这个问题之前有没有处理过？

提前致谢

Answer 1

我认为你仍然可以应用线性时间 KMP algorithm解决它。只需添加 m-1 个字符 t[0], t 1 ,...,t[m-2] 到文本 t 的末尾。当然，只有在文本 t 结束后表中仍有候选子串时才需要这样做。

如果测试字符串是 BCDEA
AXYZBCDE 应变为 AXYZBCDEAXYZ