Всем привет!

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

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

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

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

UPD2: См. также статью на Википедии по этой теме. Я являюсь основным автором текущей (29 октября 2021) версии статьи.