2模式字符串匹配算法

Question

我需要编写一个算法，用于查找最长的两个模式前缀/后缀匹配，时间复杂度为O(n+m1+m2)，其中n为字符串长度，m1和m2分别为pattern1和pattern2的长度。

例如：如果字符串是“OBANTAO”，Pattern1是“BANANA”，Patten2是“SIESTA”，那么答案就是字符串“BANTA”的子串，它由BANANA的前缀BAN和SIESTA的后缀TA组成。

Google搜索结果包括：“Rabin-karp字符串搜索算法”、“Knuth-morris-pratt算法”和“Boyer-moore字符串搜索算法”。

我能够理解以上三个算法，但问题在于，它们都是基于“单个模式前缀/后缀匹配”的。我无法将它们扩展为两个模式前缀/后缀匹配。

提供一个示例算法或搜索链接对我开发程序将非常有帮助。

- user3320657

---

你想匹配的模式总是(Pattern 1的前缀) + (pattern 2的后缀)吗？那么你真正想要的是由p1 + s2组成的最长子字符串吗？你确实需要更好地说明你的问题。 - Jim Mischel

@amit 抱歉，不是那样的。匹配的字符串应该始终是从BANANA中剪切的前缀和从SIESTA中剪切的后缀...即(B/BA/BAN/BANA/BANAN)和(A/TA/STA/ESTA/IESTA)。 - user3320657

是的，@JimMishel..你说得对..!!! - user3320657

欢迎来到StackOverflow！当回复评论时，请更新您的问题（因为这意味着您的问题没有提供足够的信息），以便对每个人更清晰，并尽可能使用代码标记使文本更易读。 - Robin

@sin，我正在处理生物（DNA / RNA /蛋白质）序列...实验结果中的样本模式可以与基因组搜索进行比较，以找到物种之间的相似之处。有许多算法可用于比较序列中的单个模式。因此，我正在进行单独的搜索，然后通过连接来比较结果以进行分析。但是，我找不到任何相关算法来实现双模式匹配程序，使用它可以使我的分析更快，更好... - user3320657

Answer 1

Knuth-Morris-Pratt算法可以很容易地进行修改，以便为干草堆字符串中的每个位置确定针线串的最长前缀长度，该前缀在该位置结束匹配。使用KMP算法来计算Pat1在String中以及reverse（String）中的反转（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"))

- David Eisenstat

---

抱歉，我无法理解您的观点。您能否给我一个示例演示？ - user3320657

我喜欢你的算法。只是想确认一下，如果我的输入是BANABTA，那么你的算法选择BANA（它没有前缀），这样可以吗？ - Mani

@Mani 我不知道，但是很容易不考虑至少一个数组为零的位置。 - David Eisenstat

@David Eisenstat..非常感谢您..!!!这真的很有用，我已经实现了它。顺便说一下，现在我能够比较两个模式，如果需要，我还会添加更多..!!!感谢所有回复的人.!!! - user3320657

Answer 2

我尝试在Java中实现@David Eisenstat的解决方案。 它的时间复杂度为O(2n)，辅助空间复杂度为O(2(n+1))。

String prefix = "BANANA";
    String suffix = "SIESTA";
    String input = "SABANANQS";

    // Prepare Inputs
    char[] prefixArray = prefix.toCharArray();
    char[] suffixArray = suffix.toCharArray();
    char[] inputArray = input.toCharArray();
    int inputLength = inputArray.length;
    int suffixLength = suffixArray.length;
    int prefixLength = prefixArray.length;
    // Auxiliary Spaces O(2(n+1))
    int[] prefixIndexs = new int[inputLength+1];
    int[] suffixIndexs = new int[inputLength+1];

    int m = 0;
    int n = 0;
    // O(1)
    for (int i = 0; i < inputLength; i++) {
        if (inputArray[i] == prefixArray[m]){
            m = m+1;
            prefixIndexs[i+1] = m;
            if (m == prefixLength) {
                m = 0;
            }
        }else{
            m = 0;
        }
        if (inputArray[inputLength-1-i] == suffixArray[suffixLength-1-n]){   // Reverse order or input and reverse oder of suffix
            n = n +1;
            suffixIndexs[i+1] = n;
            if (n == suffixLength) {
                n = 0;
            }
        }else{
            n = 0;
        }
    }

    int currmax =0;
    int mIndex = 0; // prefix Index from start
    int nIndex = 0; // suffix Index from End
    //O(1)  - Do Sum and find the max
    for (int i = 0; i < (inputLength+1); i++) {
        m = prefixIndexs[i];
        n = suffixIndexs[inputLength-i];
        if ( m != 0 && n != 0){  // if both prefix and suffix exists
            if (m+n > currmax){
                currmax = (m+n);
                mIndex = m;
                nIndex = n;
            }
        }
    }

    System.out.println("Input :"+input);
    System.out.println("prefix :"+prefix);
    System.out.println("suffix :"+suffix);
    System.out.println("max :"+currmax);
    System.out.println("mIndex :"+mIndex);
    System.out.println("nIndex :"+nIndex);
    System.out.println(prefix.substring(0,mIndex)+suffix.substring(suffix.length() - nIndex,suffix.length()));

我们可以为每个数组保留另一个数组来实现KMP算法，而不是将m和n重置为0。由于输入的前缀和后缀没有重复的字符序列，我将其留下。

- Mani