我需要为最长的两个模式前缀/后缀匹配编码算法,其时间复杂度为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种算法,但问题在于,它们都基于“单一模式前缀/后缀匹配”.我无法为两个模式前缀/后缀匹配扩展它们.
解决方法
Knuth – Morris – Pratt可以直接修改,为干草堆字符串中的每个位置产生针串的最长前缀的长度,其匹配结束于该位置.使用KMP以字符串形式计算Pat1的此信息,并以反向(字符串)反向(Pat2),然后遍历String中的每个位置,查找最大前缀/后缀长度.
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"))
