О суффиксном автомате (и дереве)

Правка ru2, от adamant, 2015-12-30 00:43:19

Всем привет!

Осенью на физтехе проходили сборы по программированию Moscow International Workshop ACM ICPC. На них мне довелось прочесть лекцию по суффиксным структурам (на самом деле, были затронуты только суффиксное дерево и суффиксный автомат). В связи с этим я хотел бы предоставить вашему вниманию конспект лекции. Собственно, вот русская и английская версии. Приятного просмотра и счастливого Нового Года :)

P.S. любая критика, предложения, пожелания и вопросы всячески приветствуются.

P. P. S. Я попытался достаточно подробно описать доказательство линейности работы, но, скорее всего, оно до сих пор тяжело воспринимается. Вы получите +100 единиц кармы, если разберётесь в нём и предложите более простой для понимания вариант :)

Теги теги_не_нужны, суффиксный автомат, суффиксное дерево

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru7 Русский adamant 2022-01-01 12:21:33 32 Мелкая правка: '.org/wiki/Suffix_automaton) по этой ' -> '.org/wiki/Суффиксный_автомат) по этой '
ru6 Русский adamant 2021-10-29 03:01:53 171
en5 Английский adamant 2021-10-29 03:01:02 171
ru5 Русский adamant 2021-10-29 02:53:06 74 ссылки протухли
en4 Английский adamant 2021-10-29 02:51:56 74 rot links fix
en3 Английский adamant 2016-01-01 14:58:39 4 Tiny change: 'Enjoy and happy holidays :)' -> 'Enjoy and Happy Holidays :)'
ru4 Русский adamant 2016-01-01 14:56:32 2 Новый Год -> Новый год
en2 Английский adamant 2015-12-30 02:16:20 127
ru3 Русский adamant 2015-12-30 02:13:34 131
ru2 Русский adamant 2015-12-30 00:43:19 26 Мелкая правка: 'просмотра :)\n\nP.' -> 'просмотра и счастливого Нового Года :)\n\nP.' (опубликовано)
en1 Английский adamant 2015-12-30 00:42:36 574 Initial revision for English translation
ru1 Русский adamant 2015-12-30 00:36:50 913 Первая редакция (сохранено в черновиках)