1

I recently studied about string matching, and was inspired to think of a similar problem. Let p be a string of m characters and t be a text of n characters. Now the problem is to find out if p occurs in t in the following way: there exists an i in the range [0, n-1] such that:

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

where i + j is computed modulo n. As an example, in normal string matching, ABCD would not occur in CDEFAB, but you can see that in the above-defined problem, ABCD would occur in CDEFAB, i = 4 in this case.

Is there any linear-time algorithm to determine if a pattern p occurs in t? And has this problem been treated before?

Thanks in advance

4

2 回答 2

1

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

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

于 2013-10-17T09:25:06.697 回答
0

只需将 t 翻倍，然后对 p 进行普通查找？

所以你会在 CDEFABCDEFAB 中查找 ABCD 并得到正确的 i。这可以在线性时间内完成。

于 2013-10-17T09:26:55.050 回答