Вычисление префикс-функции шаблона в алгоритме Кнута-Морриса-Пратта - PullRequest
Новая
       63

Вычисление префикс-функции шаблона в алгоритме Кнута-Морриса-Пратта

1 голос
/ 27 марта 2012

Есть ли какая-либо возможность в префиксной функции данного шаблона иметь что-то подобное,

0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 7 0 1 2

В приведенной выше функции префикса после 4 5 есть только вероятность 6 или 0?Если есть вероятность, например, 3 (меньше 5 и больше 0) после 4 5, как в приведенном выше примере, то каким должен быть шаблон.

Я могу думать о шаблонах, только похожих на этот, 

a b a b a b a b c a 
0 0 1 2 3 4 5 6 0 1

Спасибо.

Ответы [ 2 ]

4 голосов
/ 27 марта 2012

Вот пример шаблона, где у вас есть сбой ссылки 4 после 6: 

a b c a b c d a b c a b c a
0 0 0 1 2 3 0 1 2 3 4 5 6 4
1 голос
/ 27 марта 2012

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

0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 7 0 1 2
a b a b a c a b a b a
  1. первый символ произвольный, скажем
  2. второй символ должен отличаться от первого, иначе длина префикса будет 1
  3. третий должен совпадать с первым
  4. четвертый должен совпадать со вторым
  5. пятый должен совпадать с третьим
  6. не может быть ни одним из двух используемых на данный момент символов, a даст длину префикса 1, b - 4
  7. седьмой должен быть первым
  8. должен быть вторым
  9. должно быть третьим
  10. должно быть четвертым
  11. должно быть пятым
  12. a даст длину префикса 1, b даст 4, c даст 6, все остальное даст 0

Запись в таблице, соответствующая префиксу длины p, дает ширину самой широкой границы b этого префикса, скажем w. Следующая запись может быть только w+1 (если b является расширяемой), 0 (если не совпадает префикс) или на одну единицу больше ширины какой-либо границы b.

Так что, если table[p] содержит ширину самой широкой границы префикса length-p (с table[0] = -1), то table[p+1] является одним из 1+table[p], 1+table[table[p]], ..., 1+table[table[...[table[p]]]] = 1 + table[0] = 0 .

...