Стол Кнут-Моррис-Пратт Фэйл

Question

Я готовлюсь к экзамену и изучаю алгоритм Кнута-Морриса-Пратта. То, что будет на экзамене - это таблица ошибок и конструкция DFA. Я понимаю конструкцию DFA, но не совсем понимаю, как составить таблицу ошибок.

Если у меня есть пример шаблона "abababc", как мне построить таблицу сбоев из этого? Решение:

Таблица ошибок:

0 1 2 3 4 5 6 7

0 0 0 1 2 3 4 0

но как мне это получить? Нет кода, просто объяснение того, как получить то, что необходимо.

Answer 1

Значение ячейки i в таблице ошибок для строки s определяется следующим образом: взять подстроку s который заканчивается в положении i, а значение в ячейке - это длина самого длинного собственного (не всей строки) суффикса этой подстроки, равного его префиксу той же длины.

Давайте возьмем ваш пример и рассмотрим значение для 6, Подстрока s с длиной 6 есть ababab, У него есть 6 суффиксов: babab, abab, bab, ab а также b с другой стороны, его правильные префиксы ababa, abab, aba, ab а также a, Теперь легко увидеть, что суффиксы, равные префиксам одинаковой длины, abab а также ab, Из них дольше abab и, таким образом, значение в ячейке 6 является ее длиной - 4,

Answer 2

Шаблон P = {abababc} P[0] = 'a'. P[1] = 'b'. P[2] = "а". P[3] = 'b'. P[4] = "а". P[5] = 'b'. P[6] = 'c'.

Мотивом таблицы ошибок является определение максимально возможного сдвига (такого, чтобы мы не пропустили ни одного сопоставления с образцом, но также не делали бы ненужного сравнения), если первые символы "i" строки образца совпадают и разрыв находится у i+1-го символа.

Число в таблице сбоев указывает, сколько символов продолжает совпадать после сдвига, если первый символ i шаблона соответствует тексту.

Пусть FailTable будет FT [].

FT [1] - 'a' соответствует тексту. Обрыв найден в "b" (P[1]). У нас есть правильный суффикс "а", который соответствует правильному префиксу "а"? Ответ НЕТ. Таким образом, длина строки, которая все еще продолжает совпадать после сдвига, равна 0. Следовательно, FT [1] = 0.

FT [2] - 'ab' соответствует тексту. Обрыв найден на "а" (P[2]). У нас есть правильный суффикс "ab", который соответствует правильному префиксу "ab"? Ответ НЕТ. Таким образом, длина строки, которая все еще продолжает совпадать после сдвига, равна 0. Следовательно, FT [2] = 0.

FT [3] - 'aba' соответствует тексту. Обрыв найден на "b" (P[3]). У нас есть правильный суффикс "aba", который соответствует правильному префиксу "aba"? Ответ - ДА ("а"). Таким образом, длина строки, которая все еще продолжает совпадать после сдвига, равна 1. Следовательно, FT [3] = 1.

FT [4] - 'abab' соответствует тексту. Обрыв найден на "а" (P[4]). У нас есть правильный суффикс "abab", который соответствует правильному префиксу "abab"? Ответ - ДА ('ab'). Таким образом, длина строки, которая все еще продолжает совпадать после сдвига, равна 2. Следовательно, FT [4] = 2.

FT [5] - 'ababa' соответствует тексту. Обрыв найден на "b" (P[5]). У нас есть правильный суффикс "ababa", который соответствует правильному префиксу "ababa"? Ответ - ДА ('аба'). Таким образом, длина строки, которая все еще продолжает совпадать после сдвига, равна 3. Следовательно, FT [5] = 3.

FT [6] - 'ababab' соответствует тексту. Обрыв найден на "а" (P[6]). У нас есть правильный суффикс "ababab", который соответствует правильному префиксу "ababab"? Ответ - ДА ('abab'). Таким образом, длина строки, которая все еще продолжает совпадать после сдвига, равна 4. Следовательно, FT [6] = 4.

FT [7] - 'abababc' соответствует тексту. Перерыв не найден, шаблон соответствует тексту. У нас есть правильный суффикс "abababc", который соответствует правильному префиксу "abababc"? Ответ НЕТ. Таким образом, длина строки, которая все еще продолжает совпадать после сдвига, равна 0. Следовательно, FT[7] = 0.

Следовательно, последний массив равен FT = [0,0,1,2,3,4,0]

Надеюсь, поможет!