代码之家 › 专栏 › 技术社区 › user3320657

2模式字符串匹配算法

prefix-tree suffix-tree algorithm string regex

5

user3320657 · 技术社区 · 12 年前

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

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

谷歌的结果是:“Rabin karp字符串搜索算法”、“Knuth morris pratt算法”和“Boyer moore字符串搜索算法。”。

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

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

2 回复 | 直到 12 年前

1

3

David Eisenstat 12 年前

Knuth—Morris—Pratt可以直接修改,以在草垛串中的每个位置产生针串最长前缀的长度,匹配结束于该位置。使用KMP计算字符串中的Pat1和反向(字符串)中的Pat2的信息,然后遍历字符串中的每个位置,寻找最大前缀/后缀长度。

字符串=“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"))

2

0

Mani 12 年前

我尝试用Java实现@David Eisentat解决方案。它在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,因为输入前缀和sufix没有重复的字符序列