2模式字符串匹配算法

Question

我需要为最长的两个模式前缀/后缀匹配编码算法,其时间复杂度为O(n + m1 + m2),其中n是String的长度,m1,m2分别是pattern1和pattern2的长度.

示例:如果字符串为"OBANTAO"且Pattern1为"BANANA"且Patten2为"SIESTA",则答案为字符串的子字符串"BANTA",其由BANANA的前缀BAN和SIESTA的后缀TA组成.

谷歌的结果是:"Rabin-karp字符串搜索算法","Knuth-morris-pratt算法"和"Boyer-moore字符串搜索算法".

我能够理解以上所有3种算法,但问题在于,它们都基于"单一模式前缀/后缀匹配".我无法为两个模式前缀/后缀匹配扩展它们.

一个示例算法或搜索它的链接对我开发程序非常有帮助.

Answer 1

Knuth--Morris--Pratt 可以直接修改为，对于 haystack 字符串中的每个位置，产生以该位置结束的匹配的针字符串的最长前缀的长度。使用 KMP 计算 String 中的 Pat1 和反向(String) 中的反向(Pat2) 的此信息，然后迭代 String 中的每个位置以查找最大前缀/后缀长度。

字符串 =“OBANTAO”且 Pat1 =“BANANA”且 Pat2 =“SIESTA”的示例：

"BANANA" = Pat1 in String
 O B A N T A O
^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | |
| | | | | | | 0 ("")
| | | | | | 0 ("")
| | | | | 0 ("")
| | | | 3 ("BAN")
| | | 2 ("BA")
| | 1 ("B")
| 0 ("")
0 ("")

"ATSEIS" = reverse(Pat2) in reverse(String)
 O A T N A B O
^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | |
| | | | | | | 0 ("")
| | | | | | 0 ("")
| | | | | 1 ("A")
| | | | 0 ("")
| | | 2 ("AT")
| | 1 ("A")
| 0 ("")
0 ("")

反转第二个数组并按分量求和。

  0 0 1 2 3 0 0 0
+ 0 0 1 0 2 1 0 0
-----------------
  0 0 2 2 5 1 0 0
          ^
          |
         max (argument = "BAN" ++ reverse("AT"))