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

Revision ru4, by adamant, 2016-01-01 14:56:32

Всем привет!

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

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

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

UPD: Спасибо Burunduk1 за помощь в форматировании кода :)

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

History

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