Блог пользователя Vladik

КМП or Z-функция
Автор Vladik, 9 лет назад, По-русски

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

UPD: Всем огромное спасибо за уделённое время. Обобщив всё ниже сказанное я пришёл к выводу что они могут одно и тоже, но иногда приходится попотеть.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Yes but Z — fuction better than KMP.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Конечно, умеет. Так же как и префикс функция умеет, то что не умеет Z.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Они эквивалентны. Одну можно получить из другой

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Суф.массив <-> Суф.дерево <-> Суф.автомат, только мы же на контестах не извращаемся.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну вторую связь я не раз использовал, кстати. Проще Укконена, ИМХО

      Кстати, а можно прямо суфавтомат из суфмаса получить?)

      → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Если учесть, что префикс функция однозначно восстанавливается по Z и наоборот, то вряд ли.

→ Ответить