Алгоритм сопоставления с образцом

Question

Это слайд из класса в моем университете, он посвящен алгоритму сопоставления с образцом.

И я пытаюсь кодировать его на Java ниже;

            // Get values for both the text T1,T2 ... Tn and the pattern P1 P2 ... Pm
            String[] T = {"Java", "is", "too", "delicious", ", Dr.Java", "is", "confrim!"};
            String[] P = { "is", "too"};
            // Get values for n and m, the size of the text and the pattern, respectively
            int n = T.length;
            int m = P.length;
            // Set k1 the starting location for the attempted match, to 1
            int k = 0;

            // While(k<=(n-m+1))do
            while (k <= (n - m + 1) - 1) {
                    // Set the value of i to 1
                    int i = 0;
                    // Set the value of Mismatch NO
                    boolean Mismatch = true; // Not found (true - NO)

                    // While both (i<=m) and (Mismatch = NO) do
                    while ((i <= m - 1) && (Mismatch)) { // if Not found (true - NO)
                            // if Pi != Tk+(i-1) then
                            if (P[i].equals(T[k])) { // if Found(true)
                                    // Set Mismatch to YES
                                    Mismatch = false; // Found (false - YES)
                                    // Else
                            } else {
                                    // Increment i by 1 (to move to the next character)
                                    i = i + 1;
                            }
                            // End of the loop
                    }
                    // If mismatch = NO then
                    if (!Mismatch) { // if Found (false - YES)
                            // Print the message 'There is a match at position'
                            System.out.print("There is a match at position ");
                            // Print the value of k
                            System.out.println(k);
                    }
                    // Increment k by 1
                    k = k + 1;
                    // Enf of the loop
            }
            // Stop, we are finished

Но у меня есть вопрос! почему в версии с псевдокодом проверьте, не равен ли P T Я думаю, что было бы лучше проверить, если P равно T (Как это отличается от моей версии? Извините за мой ужасный английский)

Answer 1

Вы допустили ошибку перевода на внутреннем языке, в то время как

while ((i <= m - 1) && (Mismatch)) { // if Not found (true - NO) 

В псевдокоде было сказано, что это Mismatch=no, что будет !Mismatch

Это привело к тому, чтоВы должны были инвертировать внутреннее выражение if.

Answer 2

Псевдокод по существу проверяет каждую точку, в которой совпадение может начаться в T (1 <= k <= n-m+1), зацикливается и проверяет, соответствует ли подстрока T от k до k + m-1 P. Так как только он находитнесоответствующая буква, она останавливает проверку подстроки и увеличивает k (для проверки из следующей позиции).Это условие (T[k+i-1] != P[i]) является условием прерывания для внутреннего цикла и логическим значением, указывающим, что из текущей начальной позиции k совпадение отсутствует.

Обратите внимание, что этот алгоритм имеет сложность O(nm) что медленно.Есть более умные алгоритмы, которые могут искать в линейном времени, например, KMP.