正则表达式 – 2模式字符串匹配算法

发布时间：2020-12-14 06:08:05 所属栏目：百科来源：网络整理

导读：我需要为最长的两个模式前缀/后缀匹配编码算法,其时间复杂度为O(n m1 m2),其中n是String的长度,m1,m2分别是pattern1和pattern2的长度. 示例：如果字符串为“OBANTAO”且Pattern1为“BANANA”且Patten2为“SIESTA”,则答案为字符串的子字符串“BANTA”,其由BA

我需要为最长的两个模式前缀/后缀匹配编码算法,其时间复杂度为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"))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!