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

Автор Trytrytry, 13 лет назад, По-русски
Совсем недавно понял как работает замечательный алгоритм Кнута-Морриса-Пратта (КМП), а понял его когда нарисовал вот такую картинку и зашел:

На картинке строка abayabaxyabayaba префикс типа известен, и пытаюсь найти для следующей строки длинной j значение макс. префикса совпадающего с суффиксом.


- Накидайте пожалуйста ссылки на известные Вам задачи, ну чтобы можно было решить используя КМП или часть его.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
problemclassifier тоже выдал одну задачу
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    У меня вопрос к этой задаче и подобным ей(подобную видел на тимусе). Как решать ее без хэшей? Надо применять префикс функцию на двумерный случай или перебирать по строчке?

    Заранее благодарю.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Понял как только перебором по строчке сделать, а как префикс функцию на двумерный случай применить?
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=998

Конечно, можно решить в лоб через циклы, но я решал через КМП. 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А можно ли решить все эти задачи и с хэшами?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, в некоторых, вроде, надо будет сделать бинпоиск по длине.