Алгоритм для сопоставления двух шаблонных строк

Мне нужно написать алгоритм для самого длинного совпадения префикса / суффикса с двумя образцами, сложность которого равна O(n+m1+m2), где n - длина строки, а m1, m2 - длины pattern1 и pattern2 соответственно.

Пример: если строка - "OBANTAO", а Pattern1 - "BANANA", а Patten2 - "SIESTA", то ответом является подстрока "BANTA" строки, которая состоит из префикса BAN BANANA и суффикса TA SIESTA.

Результаты от Google: "Алгоритм поиска строки Рабина-Карпа", "Алгоритм Кнута-Морриса-Пратта" и "Алгоритм поиска строки Бойера-Мура".

Я в состоянии понять все вышеупомянутые 3 алгоритма, но проблема в том, что все они основаны на "сопоставлении одного префикса / суффикса шаблона". Я не могу расширить их для соответствия двух префиксов / суффиксов.

Пример алгоритма или ссылка на его поиск очень помогли бы мне при разработке программы.

Источник

2 ответа

Решение

Кнут-Моррис-Пратт может быть изменен напрямую, чтобы получить для каждой позиции в строке стога сена длину самого длинного префикса игольной нити с совпадением, заканчивающимся в этой позиции. Используйте KMP для вычисления этой информации для Pat1 в String и наоборот (Pat2) в обратном направлении (String), затем выполняйте итерацию по каждой позиции в 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 на Java. Это в 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, поскольку у входного префикса и суффикса нет повторяющейся последовательности символов, которую я оставил

Источник
Другие вопросы по тегам