Упрощенное построение таблицы префиксов KMP. Что было бы не так с этой реализацией? - PullRequest
Новая
       53

Упрощенное построение таблицы префиксов KMP. Что было бы не так с этой реализацией?

0 голосов
/ 09 мая 2018

Алгоритм KMP нуждается в таблице префиксов, чтобы после сбоя узнать, сколько символов можно безопасно пропустить. Общая идея таблицы префиксов заключается в том, что для заданного шаблона P в заданной позиции i с символом C будет указано, сколько общих символов имеет суффикс до C с префикс P: 

int[] T = new int[P.length()];
int i = 0;
for (int j = 1; j < P.length(); ++j) {
  if (P.charAt(j) == P.charAt(i)) {
    i++;
  } else {
    i = 0;
  }
  T[j] = i;
}

Это то, что я придумал. Я посмотрел вокруг, и реализации всегда кажутся разными. Я пытался играть с парой примеров (таких как ABABACA), но и моя реализация, и, например, эта таблица префиксов KMP , похоже, дают тот же результат.

Может ли кто-нибудь сказать мне, что является логической ошибкой в ​​моей реализации и с какими входами это может привести к ошибке при создании правильной таблицы префиксов для алгоритма KMP?

Спасибо

1 Ответ

0 голосов
/ 09 мая 2018

Для вашего алгоритма характерно, что каждая запись в таблице либо 0, либо на 1 больше, чем предыдущая запись. Поэтому задача состоит в том, чтобы найти строку, в которой запись в таблице меньше предыдущей, но не равна 0.

Одной из таких строк является "ABACABABC" (которая взята из этой статьи в Википедии ).

Таблицы префиксов: 

{0,0,1,0,1,2,3,2,0}  from the linked answer
{0,0,1,0,1,2,3,0,0}  your proposed code
               ^------different here

Интересующие записи: 3, за которыми следует 2.

Рассмотрим, что происходит, когда совпадают 7 символов. Входная строка выглядит как 

ABACABA?

где? персонаж, который не соответствует, так что? не является B. ABA? может соответствовать ABAC, поэтому длина префикса равна 3.

Теперь рассмотрим, что происходит, когда совпадают 8 символов: 

ABACABAB?

где? не является C. В этом случае AB? может соответствовать ABA, поэтому длина префикса равна 2.

Это показывает, что таблица префиксов может иметь запись, которая меньше предыдущей записи, но не 0.

...