5

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

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

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

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

一个示例算法或搜索它的链接将对我开发程序有很大帮助。

4

2 回答 2

3

Knuth--Morris--Pratt 可以直接修改，以针对 haystack 字符串中的每个位置生成针字符串的最长前缀的长度，匹配在该位置结束。使用 KMP 计算 String 中的 Pat1 和 reverse(String) 中的 reverse(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"))
于 2014-02-17T21:23:32.213 回答
0

我尝试在 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()));

代替将 m 和 n 重置为 0，我们可以为每个数组保留另一个数组来实现 KMP 算法，因为输入前缀和后缀没有重复的字符序列，我离开了它

于 2014-02-18T18:43:11.940 回答