Сопоставление строк - важная задача в информатике с широким спектром приложений, от поиска в базах данных до генетики. Для выполнения этой задачи существует множество алгоритмов, и в этой статье я расскажу вам об алгоритме Кнута Морриса Пратта (KMP).

Наивный путь

Прежде чем мы перейдем к алгоритму KMP, я хотел бы показать, как большинство людей попытаются решить проблему сопоставления строк. Я делаю это, чтобы мы могли увидеть, как KMP оптимизирует поиск.

Самый простой, но наименее эффективный метод поиска совпадений - это перебрать каждый символ в стоге сена и сравнить этот символ и символы после него с символами в игле. Приведенный ниже фрагмент кода показывает, как мы это делаем.

Хотя мы можем оптимизировать приведенный выше фрагмент, продвигая внешний цикл на один символ, сразу же обнаруживается несоответствие символов во внутреннем цикле, однако это даст нам временную сложность в наихудшем случае, равную O (nm) когда у нас есть совпадающие символы до последнего символа.

haystack = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
needle = AAAAAAAAB

Путь КМП

Алгоритм KMP просматривает стог сена и иголку слева направо, пока не будет найдено совпадение. Ниже приведен фрагмент кода с особым случаем, когда обе строки имеют одинаковую длину. Это поможет вам привыкнуть к тому, как KMP просматривает строки в поисках совпадений.

Сдвиг иглы

Теперь, когда мы видим, как KMP определяет соответствие символа, мы увидим, как KMP перемещает иголку через стог сена через O (n) время для поиска совпадений. Взгляните на приведенный ниже фрагмент кода.

примечание: алгоритм, представленный здесь, работает только для тестового примера, указанного во фрагменте после этого, и пропустит возможные совпадения в других тестовых примерах. Это сделано только для того, чтобы показать, как провести иголку в стоге сена.

Когда обнаруживается несоответствие, индекс которого больше 0, мы немедленно перемещаем стрелку к этому символу в стоге сена и начинаем наши сравнения. Если несоответствие происходит в индексе 0 иглы, мы перемещаем иглу к следующему символу после несовпадения. Это лучшая и худшая временная сложность O (n).

# HOW KMP MOVES THE NEEDLE THROUGH THE HAYSTACK
CABCDEKLSDSABCDEABCD
ABCDEABCD
CABCDEKLSDSABCDEABCD
 ABCDEABCD
CABCDEKLABCDEABCD
      ABCDEABCD
CABCDEKLABCDEABCD
       ABCDEABCD
CABCDEKLABCDEABCD
        ABCDEABCD

Префиксы и суффиксы

Несмотря на то, что приведенный выше алгоритм дает достаточно хорошую временную сложность O (n), он пропускает некоторые возможные совпадения, по-прежнему выполняет ненужные сравнения и, следовательно, не дает наилучшей эффективности. Чтобы еще больше повысить эффективность описанного выше алгоритма сопоставления строк, KMP использует правильные префиксы и суффиксы, содержащиеся в игле, чтобы избежать ненужных сравнений.

Для строки ABCDEFABCR правильные префиксы, которые у нас есть в этой строке: A, AB, ABC, ABCD, ABCDE, ABCDEF, ABCDEFA, ABCDEFAB, ABCDEFABC и суффиксы, которые у нас есть являются R, CR, BCR, ABCR, FABCR, EFABCR, DEFABCR, CDEFABCR, BCDEFABCR. Теперь мы видим, что A, AB, ABC - это правильные префиксы, которые также встречаются в суффиксах, содержащихся в строке ABCDEFABCR.

В KMP мы создаем массив, который сообщает нам, где встречаются эти правильные префиксы, которые также являются суффиксами иглы, и мы используем это для оптимизации поиска. Приведенный ниже фрагмент кода создает массив, который сообщает нам, где встречается «Самый длинный правильный префикс, который также является суффиксом (LPS)».

Использование массива LPS

Когда мы обнаруживаем несоответствие в сравниваемых символах и индекс этого символа не является первым индексом (0), мы ищем значение LPS символа перед ним, чтобы узнать, сколько символов может быть пропущен в игле. Затем мы начинаем сравнение несовпадающего символа с символом, следующим за последним пропущенным символом. Если несовпадение происходит с первым символом, мы перемещаем иглу к следующему символу в стоге сена.

# HOW KMP MOVES UTILIZES THE LPS
The LPS for ABCDEABCD = [0,0,0,0,0,1,2,3,4]
CABCDEKLSDSABCDEABCD
ABCDEABCD
CABCDEABRDABCDEABCD
 ABCDEABCD
# A and B are italicized to show that they are skipped. 
# Rather than begin comparing from index 0, we start our comparison from index 2
# The possible match AB is however not skipped even though we never compare the two characters.
CABCDEABRDABCDEABCD
      ABCDEABCD
CABCDEABRDABCDEABCD
         ABCDEABCD
CABCDEABRDABCDEABCD
          ABCDEABCD