Суфіксний автомат

Суфіксний автомат — це потужна структура даних, яка дозволяє розв'язувати багато задач, пов'язаних із рядками.

Наприклад, з його допомогою можна шукати всі входження одного рядка в інший або підраховувати кількість різних підрядків заданого рядка. Обидві задачі розв'язуються за лінійний час за допомогою суфіксного автомата.

Інтуїтивно суфіксний автомат можна розуміти як стиснуту форму всіх підрядків заданого рядка. Вражає те, що суфіксний автомат містить усю цю інформацію в дуже стиснутому вигляді. Для рядка довжини $n$ він потребує лише $O(n)$ пам'яті. Більше того, його також можна побудувати за $O(n)$ часу (якщо вважати розмір $k$ алфавіту константою), інакше і пам'ять, і часова складність становитимуть $O(n \log k)$.

Лінійність розміру суфіксного автомата вперше виявили 1983 року Blumer та інші, а 1985 року Crochemore та Blumer представили перші лінійні алгоритми його побудови.

Коли підходить цей алгоритм?

• Багато запитів про підрядки одного тексту (входження, кількість різних підрядків, найдовший спільний підрядок) за лінійний час? (якщо задача суто лексикографічна на суфіксах → Суфіксний масив)
• Структуру будуєте по одному тексту, а потім багаторазово запитуєте? (якщо багато взірців шукаєте у тексті за один прохід → Ахо-Корасік)
• Лінійних методів (КМП/хеші) недостатньо для ваших підрядкових запитів? (для простого пошуку одного взірця → КМП)

Означення суфіксного автомата

Суфіксний автомат для заданого рядка $s$ — це мінімальний DFA (детермінований скінченний автомат / детермінована скінченна машина станів), який приймає всі суфікси рядка $s$.

Іншими словами:

• Суфіксний автомат — це орієнтований ациклічний граф. Вершини називаються станами, а ребра — переходами між станами.
• Один зі станів $t_0$ є початковим станом, і він має бути джерелом графа (усі інші стани досяжні з $t_0$).
• Кожен перехід позначено деяким символом. Усі переходи, що виходять зі стану, мають мати різні позначки.
• Один або декілька станів позначено як термінальні стани. Якщо ми вирушимо з початкового стану $t_0$ і рухатимемося переходами до термінального стану, то позначки пройдених переходів мають складати один із суфіксів рядка $s$. Кожен суфікс рядка $s$ має бути виразним через деякий шлях із $t_0$ до термінального стану.
• Суфіксний автомат містить мінімальну кількість вершин серед усіх автоматів, що задовольняють описані вище умови.

Властивість підрядків

Найпростіша і найважливіша властивість суфіксного автомата полягає в тому, що він містить інформацію про всі підрядки рядка $s$. Будь-який шлях, що починається в початковому стані $t_0$, якщо записати позначки переходів, утворює підрядок рядка $s$. І навпаки, кожен підрядок рядка $s$ відповідає певному шляху, що починається в $t_0$.

Щоб спростити пояснення, будемо казати, що підрядок відповідає цьому шляху (який починається в $t_0$, і позначки якого складають цей підрядок). І навпаки, будемо казати, що будь-який шлях відповідає рядку, який складають його позначки.

До стану може вести один або декілька шляхів. Тому будемо казати, що стан відповідає множині рядків, які відповідають цим шляхам.

Приклади побудованих суфіксних автоматів

Тут ми наведемо кілька прикладів суфіксних автоматів для кількох простих рядків.

Початковий стан ми позначатимемо синім, а термінальні стани — зеленим.

Для рядка $s =~ \text{""}$:

Для рядка $s =~ \text{"a"}$:

Для рядка $s =~ \text{"aa"}$:

Для рядка $s =~ \text{"ab"}$:

Для рядка $s =~ \text{"aba"}$:

Для рядка $s =~ \text{"abb"}$:

Для рядка $s =~ \text{"abbb"}$:

Побудова за лінійний час

Перш ніж описати алгоритм побудови суфіксного автомата за лінійний час, нам потрібно ввести кілька нових понять і простих доведень, які будуть дуже важливими для розуміння побудови.

Кінцеві позиції $endpos$

Розглянемо будь-який непорожній підрядок $t$ рядка $s$. Через $endpos(t)$ ми позначатимемо множину всіх позицій у рядку $s$, в яких закінчуються входження $t$. Наприклад, для рядка $\text{"abcbc"}$ маємо $endpos(\text{"bc"}) = \{2, 4\}$.

Два підрядки $t_1$ і $t_2$ ми називатимемо $endpos$-еквівалентними, якщо їхні множини кінцевих позицій збігаються: $endpos(t_1) = endpos(t_2)$. Таким чином, усі непорожні підрядки рядка $s$ можна розбити на кілька класів еквівалентності відповідно до їхніх множин $endpos$.

Виявляється, що в суфіксному автоматі $endpos$-еквівалентні підрядки відповідають одному й тому самому стану. Іншими словами, кількість станів у суфіксному автоматі дорівнює кількості класів еквівалентності серед усіх підрядків плюс початковий стан. Кожен стан суфіксного автомата відповідає одному або кільком підрядкам, що мають однакове значення $endpos$.

Пізніше ми опишемо алгоритм побудови, користуючись цим припущенням. Тоді ми побачимо, що всі необхідні властивості суфіксного автомата, окрім мінімальності, виконуються. А мінімальність випливає з теореми Нероуда (яку ми не доводитимемо в цій статті).

Зробимо кілька важливих спостережень щодо значень $endpos$:

Лема 1: Два непорожні підрядки $u$ і $w$ (де $length(u) \le length(w)$) є $endpos$-еквівалентними тоді й лише тоді, коли рядок $u$ зустрічається в $s$ лише у вигляді суфікса рядка $w$.

Доведення очевидне. Якщо $u$ і $w$ мають однакові значення $endpos$, то $u$ є суфіксом $w$ і з'являється в $s$ лише у вигляді суфікса $w$. А якщо $u$ є суфіксом $w$ і з'являється в $s$ лише у вигляді суфікса, то значення $endpos$ рівні за означенням.

Лема 2: Розглянемо два непорожні підрядки $u$ і $w$ (де $length(u) \le length(w)$). Тоді їхні множини $endpos$ або зовсім не перетинаються, або $endpos(w)$ є підмножиною $endpos(u)$. А це залежить від того, чи є $u$ суфіксом $w$, чи ні.

$$\begin{cases} endpos(w) \subseteq endpos(u) & \text{якщо } u \text{ є суфіксом } w \\\\ endpos(w) \cap endpos(u) = \emptyset & \text{інакше} \end{cases}$$

Доведення: Якщо множини $endpos(u)$ і $endpos(w)$ мають принаймні один спільний елемент, то рядки $u$ і $w$ обидва закінчуються в цій позиції, тобто $u$ є суфіксом $w$. Але тоді при кожному входженні $w$ також з'являється підрядок $u$, а це означає, що $endpos(w)$ є підмножиною $endpos(u)$.

Лема 3: Розглянемо $endpos$-клас еквівалентності. Відсортуємо всі підрядки цього класу за спаданням довжини. Тоді в отриманій послідовності кожен підрядок буде на один коротшим за попередній і водночас буде суфіксом попереднього. Іншими словами, в одному класі еквівалентності коротші підрядки фактично є суфіксами довших підрядків і набувають усіх можливих довжин на певному проміжку $[x; y]$.

Доведення: Зафіксуємо деякий $endpos$-клас еквівалентності. Якщо він містить лише один рядок, то лема очевидно правильна. Тепер припустимо, що кількість рядків у класі більша за один.

Згідно з Лемою 1, два різні $endpos$-еквівалентні рядки завжди такі, що коротший є власним суфіксом довшого. Отже, у класі еквівалентності не може бути двох рядків однакової довжини.

Позначимо через $w$ найдовший, а через $u$ найкоротший рядок у класі еквівалентності. Згідно з Лемою 1, рядок $u$ є власним суфіксом рядка $w$. Розглянемо тепер будь-який суфікс $w$ з довжиною в проміжку $[length(u); length(w)]$. Легко бачити, що цей суфікс також міститься в тому самому класі еквівалентності. Адже цей суфікс може з'являтися в рядку $s$ лише у вигляді суфікса $w$ (оскільки й коротший суфікс $u$ зустрічається в $s$ лише у вигляді суфікса $w$). Отже, згідно з Лемою 1, цей суфікс є $endpos$-еквівалентним рядку $w$.

Суфіксні посилання $link$

Розглянемо деякий стан $v \ne t_0$ в автоматі. Як ми знаємо, стан $v$ відповідає класу рядків з однаковими значеннями $endpos$. І якщо ми позначимо через $w$ найдовший із цих рядків, то всі інші рядки є суфіксами $w$.

Ми також знаємо, що кілька перших суфіксів рядка $w$ (якщо розглядати суфікси в порядку спадання їхньої довжини) усі містяться в цьому класі еквівалентності, а всі інші суфікси (принаймні один — порожній суфікс) перебувають у деяких інших класах. Позначимо через $t$ найбільший такий суфікс і зробимо до нього суфіксне посилання.

Іншими словами, суфіксне посилання $link(v)$ веде до стану, який відповідає найдовшому суфіксу рядка $w$, що перебуває в іншому $endpos$-класі еквівалентності.

Тут ми вважаємо, що початковий стан $t_0$ відповідає власному класу еквівалентності (що містить лише порожній рядок), і для зручності покладаємо $endpos(t_0) = \{-1, 0, \dots, length(s)-1\}$.

Лема 4: Суфіксні посилання утворюють дерево з коренем $t_0$.

Доведення: Розглянемо довільний стан $v \ne t_0$. Суфіксне посилання $link(v)$ веде до стану, що відповідає рядкам зі строго меншою довжиною (це випливає з означення суфіксних посилань і з Леми 3). Тому, рухаючись суфіксними посиланнями, ми рано чи пізно прийдемо до початкового стану $t_0$, який відповідає порожньому рядку.

Лема 5: Якщо ми побудуємо дерево за допомогою множин $endpos$ (за правилом, що множина батьківського вузла містить множини всіх дітей як підмножини), то ця структура збігатиметься з деревом суфіксних посилань.

Доведення: Те, що ми можемо побудувати дерево за допомогою множин $endpos$, випливає безпосередньо з Леми 2 (будь-які дві множини або не перетинаються, або одна міститься в іншій).

Розглянемо тепер довільний стан $v \ne t_0$ і його суфіксне посилання $link(v)$. З означення суфіксного посилання і з Леми 2 випливає, що

$$endpos(v) \subseteq endpos(link(v)),$$

що разом з попередньою лемою доводить твердження: дерево суфіксних посилань по суті є деревом множин $endpos$.

Ось приклад дерева суфіксних посилань у суфіксному автоматі, побудованому для рядка $\text{"abcbc"}$. Вузли позначено найдовшим підрядком із відповідного класу еквівалентності.

Підсумок

Перш ніж переходити до самого алгоритму, підсумуємо накопичені знання і введемо кілька допоміжних позначень.

• Підрядки рядка $s$ можна розбити на класи еквівалентності відповідно до їхніх кінцевих позицій $endpos$.
• Суфіксний автомат складається з початкового стану $t_0$, а також з одного стану для кожного $endpos$-класу еквівалентності.
• Кожному стану $v$ відповідає один або декілька підрядків. Через $longest(v)$ ми позначатимемо найдовший такий рядок, а через $len(v)$ — його довжину. Через $shortest(v)$ ми позначатимемо найкоротший такий підрядок, а його довжину — через $minlen(v)$. Тоді всі рядки, що відповідають цьому стану, є різними суфіксами рядка $longest(v)$ і мають усі можливі довжини на проміжку $[minlen(v); len(v)]$.
• Для кожного стану $v \ne t_0$ суфіксне посилання визначається як посилання, що веде до стану, який відповідає суфіксу рядка $longest(v)$ довжини $minlen(v) - 1$. Суфіксні посилання утворюють дерево з коренем у $t_0$, і водночас це дерево утворює відношення включення між множинами $endpos$.
• Ми можемо виразити $minlen(v)$ для $v \ne t_0$ через суфіксне посилання $link(v)$ так:

$$minlen(v) = len(link(v)) + 1$$

• Якщо ми почнемо з довільного стану $v_0$ і рухатимемося суфіксними посиланнями, то рано чи пізно досягнемо початкового стану $t_0$. При цьому ми отримаємо послідовність неперетинних проміжків $[minlen(v_i); len(v_i)]$, які в об'єднанні утворюють неперервний проміжок $[0; len(v_0)]$.

Алгоритм

Тепер ми можемо перейти до самого алгоритму. Алгоритм буде онлайновим, тобто ми додаватимемо символи рядка по одному і на кожному кроці відповідно модифікуватимемо автомат.

Щоб досягти лінійного споживання пам'яті, у кожному стані ми зберігатимемо лише значення $len$, $link$ і список переходів. Ми не будемо позначати термінальні стани (але пізніше покажемо, як розставити ці позначки після побудови суфіксного автомата).

Спочатку автомат складається з одного стану $t_0$, який матиме індекс $0$ (решта станів отримають індекси $1, 2, \dots$). Для зручності призначаємо йому $len = 0$ і $link = -1$ ($-1$ буде фіктивним, неіснуючим станом).

Тепер уся задача зводиться до реалізації процесу додавання одного символу $c$ до кінця поточного рядка. Опишемо цей процес:

• Нехай $last$ — стан, що відповідає всьому рядку до додавання символу $c$. (Спочатку покладаємо $last = 0$, і відповідно змінюватимемо $last$ на останньому кроці алгоритму.)

• Створюємо новий стан $cur$ і призначаємо йому $len(cur) = len(last) + 1$. Значення $link(cur)$ на цей момент невідоме.

• Тепер виконуємо таку процедуру: Починаємо зі стану $last$. Доки немає переходу за буквою $c$, ми додаватимемо перехід до стану $cur$ і йтимемо суфіксним посиланням. Якщо в якийсь момент перехід за буквою $c$ уже існує, то ми зупиняємося і позначаємо цей стан через $p$.

• Якщо ми не знайшли такого стану $p$, тобто дійшли до фіктивного стану $-1$, то ми можемо просто покласти $link(cur) = 0$ і завершити.

• Припустимо тепер, що ми знайшли стан $p$, з якого існує перехід за буквою $c$. Стан, до якого веде цей перехід, ми позначимо через $q$.

• Тепер маємо два випадки. Або $len(p) + 1 = len(q)$, або ні.

• Якщо $len(p) + 1 = len(q)$, то ми можемо просто покласти $link(cur) = q$ і завершити.

• Інакше все трохи складніше. Необхідно клонувати стан $q$: ми створюємо новий стан $clone$, копіюємо всі дані з $q$ (суфіксне посилання й переходи), окрім значення $len$. Покладаємо $len(clone) = len(p) + 1$.

  Після клонування ми спрямовуємо суфіксне посилання з $cur$ на $clone$, а також з $q$ на clone.

  Нарешті, нам потрібно пройтися зі стану $p$ назад суфіксними посиланнями, доки існує перехід за $c$ до стану $q$, і перенаправити всі ці переходи на стан $clone$.

• У будь-якому з трьох випадків після завершення процедури ми оновлюємо значення $last$ станом $cur$.

Якщо ми також хочемо знати, які стани є термінальними, а які ні, то можемо знайти всі термінальні стани після побудови повного суфіксного автомата для всього рядка $s$. Для цього ми беремо стан, що відповідає всьому рядку (збережений у змінній $last$), і йдемо його суфіксними посиланнями, доки не досягнемо початкового стану. Усі відвідані стани ми позначимо як термінальні. Легко зрозуміти, що в такий спосіб ми позначимо саме ті стани, що відповідають усім суфіксам рядка $s$, а це і є термінальні стани.

У наступному розділі ми детально розглянемо кожен крок і покажемо його коректність.

Тут лише зауважимо, що оскільки ми створюємо лише один або два нові стани на кожен символ $s$, суфіксний автомат містить лінійну кількість станів.

Лінійність кількості переходів і взагалі лінійність часу роботи алгоритму менш очевидні, і їх ми доведемо після того, як доведемо коректність.

Коректність

• Перехід $(p, q)$ ми називатимемо неперервним, якщо $len(p) + 1 = len(q)$. Інакше, тобто коли $len(p) + 1 < len(q)$, перехід називатимемо розривним.

  Як видно з опису алгоритму, неперервні й розривні переходи приводять до різних випадків алгоритму. Неперервні переходи зафіксовані й більше ніколи не змінюються. Натомість розривні переходи можуть змінюватися, коли до рядка додаються нові букви (кінець ребра переходу може змінюватися).

• Щоб уникнути неоднозначності, рядок, для якого було побудовано суфіксний автомат до додавання поточного символу $c$, ми позначатимемо через $s$.

• Алгоритм починається зі створення нового стану $cur$, який відповідатиме всьому рядку $s + c$. Зрозуміло, чому ми маємо створити новий стан. Разом із новим символом створюється новий клас еквівалентності.

• Після створення нового стану ми проходимо суфіксними посиланнями, починаючи зі стану, що відповідає всьому рядку $s$. Для кожного стану ми намагаємося додати перехід із символом $c$ до нового стану $cur$. Таким чином ми дописуємо до кожного суфікса рядка $s$ символ $c$. Однак ми можемо додавати ці нові переходи лише тоді, коли вони не конфліктують із уже наявним. Тому, як тільки ми знаходимо вже наявний перехід за $c$, ми маємо зупинитися.

• У найпростішому випадку ми дійшли до фіктивного стану $-1$. Це означає, що ми додали перехід за $c$ до всіх суфіксів рядка $s$. Це також означає, що символ $c$ раніше не входив до рядка $s$. Тому суфіксне посилання $cur$ має вести до стану $0$.

• У другому випадку ми натрапили на наявний перехід $(p, q)$. Це означає, що ми спробували додати до машини рядок $x + c$ (де $x$ — суфікс рядка $s$), який уже існує в машині (рядок $x + c$ уже зустрічається як підрядок $s$). Оскільки ми припускаємо, що автомат для рядка $s$ побудовано правильно, новий перехід тут додавати не слід.

  Однак тут є складність. До якого стану має вести суфіксне посилання зі стану $cur$? Ми маємо зробити суфіксне посилання до стану, в якому найдовший рядок — це саме $x + c$, тобто $len$ цього стану має дорівнювати $len(p) + 1$. Однак можливо, що такого стану ще не існує, тобто $len(q) > len(p) + 1$. У цьому випадку нам доведеться створити такий стан, розщепивши стан $q$.

• Якщо перехід $(p, q)$ виявляється неперервним, то $len(q) = len(p) + 1$. У цьому випадку все просто. Ми спрямовуємо суфіксне посилання з $cur$ на стан $q$.

• Інакше перехід є розривним, тобто $len(q) > len(p) + 1$. Це означає, що стан $q$ відповідає не лише суфіксу рядка $s + c$ довжини $len(p) + 1$, а й довшим підрядкам рядка $s$. Нам не лишається нічого іншого, окрім як розщепити стан $q$ на два підстани так, щоб перший мав довжину $len(p) + 1$.

  Як можна розщепити стан? Ми клонуємо стан $q$, що дає нам стан $clone$, і покладаємо $len(clone) = len(p) + 1$. Ми копіюємо всі переходи з $q$ до $clone$, бо не хочемо змінювати шляхи, що проходять через $q$. Також ми встановлюємо суфіксне посилання з $clone$ на ціль суфіксного посилання $q$, а суфіксне посилання $q$ — на $clone$.

  І після розщеплення стану ми встановлюємо суфіксне посилання з $cur$ на $clone$.

  На останньому кроці ми змінюємо деякі переходи до $q$, перенаправляючи їх на $clone$. Які переходи ми маємо змінити? Достатньо перенаправити лише переходи, що відповідають усім суфіксам рядка $w + c$ (де $w$ — найдовший рядок $p$), тобто нам потрібно продовжувати рух суфіксними посиланнями, починаючи з вершини $p$, доки ми не досягнемо фіктивного стану $-1$ або переходу, що веде до іншого стану, ніж $q$.

Лінійна кількість операцій

Спочатку ми одразу робимо припущення, що розмір алфавіту сталий. Якщо це не так, то про лінійну часову складність говорити не вдасться. Список переходів з однієї вершини зберігатиметься у збалансованому дереві, що дозволяє швидко виконувати операції пошуку за ключем і додавання ключів. Тому якщо ми позначимо через $k$ розмір алфавіту, то асимптотична поведінка алгоритму буде $O(n \log k)$ з $O(n)$ пам'яті. Однак якщо алфавіт достатньо малий, то можна пожертвувати пам'яттю, відмовившись від збалансованих дерев, і зберігати переходи в кожній вершині як масив довжини $k$ (для швидкого пошуку за ключем) і динамічний список (для швидкого обходу всіх наявних ключів). Так ми досягаємо часової складності $O(n)$ для алгоритму, але ціною складності пам'яті $O(n k)$.

Отже, ми вважатимемо розмір алфавіту сталим, тобто кожну операцію пошуку переходу за символом, додавання переходу, пошуку наступного переходу — усі ці операції можна виконати за $O(1)$.

Якщо ми розглянемо всі частини алгоритму, то він містить три місця, в яких лінійна складність не очевидна:

• Перше місце — обхід суфіксними посиланнями зі стану $last$ із додаванням переходів із символом $c$.
• Друге місце — копіювання переходів, коли стан $q$ клонується в новий стан $clone$.
• Третє місце — зміна переходів, що ведуть до $q$, з перенаправленням їх на $clone$.

Ми користуємося тим фактом, що розмір суфіксного автомата (як за кількістю станів, так і за кількістю переходів) є лінійним. (Доведенням лінійності кількості станів є сам алгоритм, а доведення лінійності кількості станів наведено нижче, після реалізації алгоритму.)

Таким чином, загальна складність першого і другого місць очевидна, адже кожна операція додає лише один амортизований новий перехід до автомата.

Залишається оцінити загальну складність третього місця, в якому ми перенаправляємо переходи, що спочатку вказували на $q$, на $clone$. Позначимо $v = longest(p)$. Це суфікс рядка $s$, і з кожною ітерацією його довжина зменшується — а отже, позиція $v$ як суфікса рядка $s$ монотонно зростає з кожною ітерацією. У цьому випадку, якщо перед першою ітерацією циклу відповідний рядок $v$ перебував на глибині $k$ ($k \ge 2$) від $last$ (рахуючи глибину як кількість суфіксних посилань), то після останньої ітерації рядок $v + c$ буде $2$-м суфіксним посиланням на шляху від $cur$ (який стане новим значенням $last$).

Таким чином, кожна ітерація цього циклу призводить до того, що позиція рядка $longest(link(link(last))$ як суфікса поточного рядка монотонно зростає. Тому цей цикл не може виконатися більш ніж $n$ ітерацій, що й потрібно було довести.

Реалізація

Спочатку опишемо структуру даних, яка зберігатиме всю інформацію про конкретний перехід ($len$, $link$ і список переходів). За потреби сюди можна додати прапорець термінального стану, а також іншу інформацію. Список переходів ми зберігатимемо у вигляді $map$, що дозволяє нам досягти сумарно $O(n)$ пам'яті та $O(n \log k)$ часу на обробку всього рядка.

C++

struct state {
    int len, link;
    map<char, int> next;
};

Python

# C++ map<char,int> передаємо як звичайний dict[str,int]:
# ключі — односимвольні рядки, значення — індекси станів.
# len і link тримаємо окремими списками (st_len, st_link),
# а переходи — списком словників st_next, де st_next[v][c] = індекс.
class State:
    def __init__(self):
        self.len = 0
        self.link = -1
        self.next: dict[str, int] = {}

TypeScript

// C++ map<char,int> моделюємо як Map<string, number>:
// ключ — односимвольний рядок (TS не має окремого типу char).
interface State {
    len: number;
    link: number;
    next: Map<string, number>;
}

Go

// C++ map<char,int> у Go — це map[byte]int:
// у Go рядок індексується байтами, тож символ зручно тримати як byte.
type state struct {
    length int // len — зарезервоване ім'я вбудованої функції, тому length
    link   int
    next   map[byte]int
}

Сам суфіксний автомат зберігатиметься в масиві цих структур $state$. Ми зберігаємо поточний розмір $sz$, а також змінну $last$ — стан, що відповідає всьому рядку на цей момент.

C++

const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;

Python

# Замість статичного масиву на MAXLEN*2 використовуємо динамічний список,
# який зростає під час побудови. sz і last — глобальний стан автомата.
MAXLEN = 100000
st: list[State] = []
sz = 0
last = 0

TypeScript

// Замість статичного масиву використовуємо динамічний st, що зростає
// під час побудови. sz і last — поточний стан автомата.
const MAXLEN = 100000;
let st: State[] = [];
let sz = 0;
let last = 0;

Go

// Замість статичного масиву використовуємо зріз, який нарощуємо append-ом.
const MAXLEN = 100000

var st []state
var sz, last int

Наведемо функцію, що ініціалізує суфіксний автомат (створює суфіксний автомат з одним станом).

C++

void sa_init() {
    st[0].len = 0;
    st[0].link = -1;
    sz++;
    last = 0;
}

Python

def sa_init():
    global sz, last, st
    st = [State()]          # початковий стан t0
    st[0].len = 0
    st[0].link = -1
    sz = 1
    last = 0

TypeScript

function saInit(): void {
    st = [{ len: 0, link: -1, next: new Map() }]; // початковий стан t0
    sz = 1;
    last = 0;
}

Go

func saInit() {
    // Виділяємо ємність наперед, щоб уникнути зайвих перевиділень.
    st = make([]state, 1, MAXLEN*2)
    st[0].length = 0
    st[0].link = -1
    st[0].next = make(map[byte]int) // нульове значення map у Go — nil, тож ініціалізуємо
    sz = 1
    last = 0
}

І нарешті наведемо реалізацію головної функції — яка додає наступний символ до кінця поточного рядка, відповідно перебудовуючи машину.

C++

void sa_extend(char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    while (p != -1 && !st[p].next.count(c)) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) {
        st[cur].link = 0;
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
            st[cur].link = q;
        } else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

Python

def sa_extend(c: str):
    global sz, last
    cur = sz
    st.append(State())              # створюємо новий стан cur
    sz += 1
    st[cur].len = st[last].len + 1
    p = last
    while p != -1 and c not in st[p].next:
        st[p].next[c] = cur
        p = st[p].link
    if p == -1:
        st[cur].link = 0
    else:
        q = st[p].next[c]
        if st[p].len + 1 == st[q].len:
            st[cur].link = q
        else:
            clone = sz
            st.append(State())      # клон стану q
            sz += 1
            st[clone].len = st[p].len + 1
            st[clone].next = dict(st[q].next)  # копія словника переходів
            st[clone].link = st[q].link
            while p != -1 and st[p].next.get(c) == q:
                st[p].next[c] = clone
                p = st[p].link
            st[q].link = clone
            st[cur].link = clone
    last = cur

TypeScript

function saExtend(c: string): void {
    const cur = sz++;
    st.push({ len: 0, link: -1, next: new Map() }); // новий стан cur
    st[cur].len = st[last].len + 1;
    let p = last;
    while (p !== -1 && !st[p].next.has(c)) {
        st[p].next.set(c, cur);
        p = st[p].link;
    }
    if (p === -1) {
        st[cur].link = 0;
    } else {
        const q = st[p].next.get(c)!;
        if (st[p].len + 1 === st[q].len) {
            st[cur].link = q;
        } else {
            const clone = sz++;
            st.push({                       // клон стану q
                len: st[p].len + 1,
                link: st[q].link,
                next: new Map(st[q].next),  // копія переходів
            });
            while (p !== -1 && st[p].next.get(c) === q) {
                st[p].next.set(c, clone);
                p = st[p].link;
            }
            st[q].link = clone;
            st[cur].link = clone;
        }
    }
    last = cur;
}

Go

func saExtend(c byte) {
    cur := sz
    sz++
    st = append(st, state{link: -1, next: make(map[byte]int)}) // новий стан cur
    st[cur].length = st[last].length + 1
    p := last
    for p != -1 {
        if _, ok := st[p].next[c]; ok {
            break
        }
        st[p].next[c] = cur
        p = st[p].link
    }
    if p == -1 {
        st[cur].link = 0
    } else {
        q := st[p].next[c]
        if st[p].length+1 == st[q].length {
            st[cur].link = q
        } else {
            clone := sz
            sz++
            // копіюємо переходи q у новий map (мапи у Go — посилальні)
            cloneNext := make(map[byte]int, len(st[q].next))
            for k, v := range st[q].next {
                cloneNext[k] = v
            }
            st = append(st, state{
                length: st[p].length + 1,
                link:   st[q].link,
                next:   cloneNext,
            })
            for p != -1 && st[p].next[c] == q {
                st[p].next[c] = clone
                p = st[p].link
            }
            st[q].link = clone
            st[cur].link = clone
        }
    }
    last = cur
}

Як зазначено вище, якщо пожертвувати пам'яттю ($O(n k)$, де $k$ — розмір алфавіту), то можна досягти часу побудови машини $O(n)$ навіть для будь-якого розміру алфавіту $k$. Але для цього доведеться зберігати в кожному стані масив розміру $k$ (для швидкого переходу до переходу за буквою) і додатково список усіх переходів (для швидкого ітерування по переходах).

Додаткові властивості

Кількість станів

Кількість станів у суфіксному автоматі рядка $s$ довжини $n$ не перевищує $2n - 1$ (для $n \ge 2$).

Доведенням є сам алгоритм побудови, оскільки спочатку автомат складається з одного стану, на першій і другій ітерації створюється лише один стан, а на решті $n-2$ кроків створюється щонайбільше $2$ стани на кожному.

Однак ми можемо також показати цю оцінку без знання алгоритму. Нагадаємо, що кількість станів дорівнює кількості різних множин $endpos$. Крім того, ці множини $endpos$ утворюють дерево (батьківська вершина містить у своїй множині всі дочірні множини). Розглянемо це дерево і трохи його перетворимо: доки в ньому є внутрішня вершина лише з однією дитиною (а це означає, що множина дитини не містить принаймні однієї позиції з батьківської множини), ми створюємо нову дитину з множиною відсутніх позицій. Зрештою ми отримуємо дерево, в якому кожна внутрішня вершина має степінь більший за один, а кількість листків не перевищує $n$. Тому в такому дереві не більш ніж $2n - 1$ вершин.

Цю межу кількості станів насправді можна досягти для кожного $n$. Можливий рядок такий:

$$\text{"abbb}\dots \text{bbb"}$$

На кожній ітерації, починаючи з третьої, алгоритм розщеплюватиме стан, унаслідок чого вийде рівно $2n - 1$ станів.

Кількість переходів

Кількість переходів у суфіксному автоматі рядка $s$ довжини $n$ не перевищує $3n - 4$ (для $n \ge 3$).

Доведемо це:

Спочатку оцінимо кількість неперервних переходів. Розглянемо кістякове дерево найдовших шляхів в автоматі, що починаються у стані $t_0$. Цей каркас складатиметься лише з неперервних ребер, а тому їхня кількість менша за кількість станів, тобто не перевищує $2n - 2$.

Тепер оцінимо кількість розривних переходів. Нехай поточний розривний перехід — це $(p, q)$ із символом $c$. Візьмемо відповідний рядок $u + c + w$, де рядок $u$ відповідає найдовшому шляху з початкового стану до $p$, а $w$ — найдовшому шляху з $q$ до будь-якого термінального стану. З одного боку, кожен такий рядок $u + c + w$ для кожного неповного рядка буде різним (оскільки рядки $u$ і $w$ утворюються лише повними переходами). З іншого боку, кожен такий рядок $u + c + w$ за означенням термінальних станів буде суфіксом усього рядка $s$. Оскільки існує лише $n$ непорожніх суфіксів $s$, а жоден із рядків $u + c + w$ не може містити $s$ (бо весь рядок містить лише повні переходи), загальна кількість неповних переходів не перевищує $n - 1$.

Поєднання цих двох оцінок дає нам межу $3n - 3$. Однак, оскільки максимальної кількості станів можна досягти лише на тесті $\text{"abbb\dots bbb"}$, а цей випадок очевидно має менше за $3n - 3$ переходів, ми отримуємо точнішу межу $3n - 4$ для кількості переходів у суфіксному автоматі.

Цю межу також можна досягти рядком:

$$\text{"abbb}\dots \text{bbbc"}$$

Застосування

Тут ми розглянемо деякі задачі, які можна розв'язати за допомогою суфіксного автомата. Для простоти ми вважаємо розмір алфавіту $k$ сталим, що дозволяє нам вважати складність дописування символу й обходу сталою.

Перевірка входження

Дано текст $T$ і кілька взірців $P$. Нам потрібно перевірити, чи з'являються рядки $P$ як підрядок $T$.

Ми будуємо суфіксний автомат тексту $T$ за $O(length(T))$ часу. Щоб перевірити, чи з'являється взірець $P$ у $T$, ми йдемо переходами, починаючи з $t_0$, відповідно до символів $P$. Якщо в якийсь момент переходу не існує, то взірець $P$ не з'являється як підрядок $T$. Якщо ми можемо обробити в такий спосіб увесь рядок $P$, то рядок з'являється в $T$.

Зрозуміло, що це займе $O(length(P))$ часу для кожного рядка $P$. Більше того, цей алгоритм фактично знаходить довжину найдовшого префікса $P$, що з'являється в тексті.

Кількість різних підрядків

Дано рядок $S$. Потрібно обчислити кількість різних підрядків.

Побудуємо суфіксний автомат для рядка $S$.

Кожен підрядок $S$ відповідає деякому шляху в автоматі. Тому кількість різних підрядків дорівнює кількості різних шляхів в автоматі, що починаються в $t_0$.

Оскільки суфіксний автомат є орієнтованим ациклічним графом, кількість різних шляхів можна обчислити за допомогою динамічного програмування.

А саме, нехай $d[v]$ — кількість шляхів, що починаються у стані $v$ (включно зі шляхом нульової довжини). Тоді маємо рекурсію:

$$d[v] = 1 + \sum_{w : (v, w, c) \in DAWG} d[w]$$

Тобто $d[v]$ можна виразити як суму відповідей для всіх кінців переходів $v$.

Кількість різних підрядків — це значення $d[t_0] - 1$ (оскільки порожній підрядок ми не рахуємо).

Загальна часова складність: $O(length(S))$

Як альтернативу, ми можемо скористатися тим, що кожному стану $v$ відповідають підрядки довжини $[minlen(v),len(v)]$. Тому, з огляду на $minlen(v) = 1 + len(link(v))$, маємо, що загальна кількість різних підрядків у стані $v$ становить $len(v) - minlen(v) + 1 = len(v) - (1 + len(link(v))) + 1 = len(v) - len(link(v))$.

Це лаконічно продемонстровано нижче:

C++

long long get_diff_strings(){
    long long tot = 0;
    for(int i = 1; i < sz; i++) {
        tot += st[i].len - st[st[i].link].len;
    }
    return tot;
}

Python

def get_diff_strings() -> int:
    # У Python цілі необмежені, тож переповнення long long тут неактуальне.
    tot = 0
    for i in range(1, sz):
        tot += st[i].len - st[st[i].link].len
    return tot

TypeScript

function getDiffStrings(): bigint {
    // Використовуємо bigint, бо кількість підрядків може перевищити 2^53.
    let tot = 0n;
    for (let i = 1; i < sz; i++) {
        tot += BigInt(st[i].len - st[st[i].link].len);
    }
    return tot;
}

Go

func getDiffStrings() int64 {
    var tot int64
    for i := 1; i < sz; i++ {
        tot += int64(st[i].length - st[st[i].link].length)
    }
    return tot
}

Хоча це теж $O(length(S))$, цей підхід не потребує додаткової пам'яті й рекурсивних викликів, а отже, на практиці працює швидше.

Сумарна довжина всіх різних підрядків

Дано рядок $S$. Ми хочемо обчислити сумарну довжину всіх його різних підрядків.

Розв'язок схожий на попередній, тільки тепер для частини з динамічним програмуванням необхідно розглядати дві величини: кількість різних підрядків $d[v]$ та їхню сумарну довжину $ans[v]$.

Як обчислювати $d[v]$, ми вже описали в попередній задачі. Значення $ans[v]$ можна обчислити за допомогою рекурсії:

$$ans[v] = \sum_{w : (v, w, c) \in DAWG} d[w] + ans[w]$$

Ми беремо відповідь кожної суміжної вершини $w$ і додаємо до неї $d[w]$ (оскільки кожен підрядок на один символ довший, коли починається зі стану $v$).

І знову цю задачу можна обчислити за $O(length(S))$ часу.

Як альтернативу, ми можемо знову скористатися тим, що кожному стану $v$ відповідають підрядки довжини $[minlen(v),len(v)]$. Оскільки $minlen(v) = 1 + len(link(v))$ і за формулою суми арифметичної прогресії $S_n = n \cdot \frac{a_1+a_n}{2}$ (де $S_n$ позначає суму $n$ доданків, $a_1$ — перший доданок, а $a_n$ — останній доданок), ми можемо обчислити сумарну довжину підрядків у стані за сталий час. Потім ми підсумовуємо ці суми для кожного стану $v \neq t_0$ в автоматі. Це показано в коді нижче:

C++

long long get_tot_len_diff_substings() {
    long long tot = 0;
    for(int i = 1; i < sz; i++) {
        long long shortest = st[st[i].link].len + 1;
        long long longest = st[i].len;
        
        long long num_strings = longest - shortest + 1;
        long long cur = num_strings * (longest + shortest) / 2;
        tot += cur;
    }
    return tot;
}

Python

def get_tot_len_diff_substings() -> int:
    tot = 0
    for i in range(1, sz):
        shortest = st[st[i].link].len + 1
        longest = st[i].len
        num_strings = longest - shortest + 1
        # сума арифметичної прогресії; // — цілочисельне ділення
        cur = num_strings * (longest + shortest) // 2
        tot += cur
    return tot

TypeScript

function getTotLenDiffSubstings(): bigint {
    let tot = 0n;
    for (let i = 1; i < sz; i++) {
        const shortest = BigInt(st[st[i].link].len + 1);
        const longest = BigInt(st[i].len);
        const numStrings = longest - shortest + 1n;
        // у bigint ділення / уже цілочисельне
        const cur = (numStrings * (longest + shortest)) / 2n;
        tot += cur;
    }
    return tot;
}

Go

func getTotLenDiffSubstings() int64 {
    var tot int64
    for i := 1; i < sz; i++ {
        shortest := int64(st[st[i].link].length + 1)
        longest := int64(st[i].length)

        numStrings := longest - shortest + 1
        cur := numStrings * (longest + shortest) / 2
        tot += cur
    }
    return tot
}

Цей підхід працює за $O(length(S))$ часу, але експериментально працює у 20 разів швидше за версію з мемоїзованим динамічним програмуванням на випадкових рядках. Він не потребує додаткової пам'яті й рекурсії.

Лексикографічно $k$-й підрядок

Дано рядок $S$. Нам потрібно відповісти на кілька запитів. Для кожного заданого числа $K_i$ ми маємо знайти $K_i$-й рядок у лексикографічно впорядкованому списку всіх підрядків.

Розв'язок цієї задачі ґрунтується на ідеї двох попередніх задач. Лексикографічно $k$-й підрядок відповідає лексикографічно $k$-му шляху в суфіксному автоматі. Тому, підрахувавши кількість шляхів з кожного стану, ми можемо легко шукати $k$-й шлях, починаючи з кореня автомата.

Це займає $O(length(S))$ часу на попередню обробку, а потім $O(length(ans) \cdot k)$ на кожен запит (де $ans$ — відповідь на запит, а $k$ — розмір алфавіту).

Найменший циклічний зсув

Дано рядок $S$. Ми хочемо знайти лексикографічно найменший циклічний зсув.

Ми будуємо суфіксний автомат для рядка $S + S$. Тоді автомат міститиме в собі як шляхи всі циклічні зсуви рядка $S$.

Отже, задача зводиться до пошуку лексикографічно найменшого шляху довжини $length(S)$, що можна зробити тривіально: ми починаємо в початковому стані й жадібно проходимо переходами з мінімальним символом.

Загальна часова складність — $O(length(S))$.

Кількість входжень

Дано текст $T$. Нам потрібно відповісти на кілька запитів. Для кожного заданого взірця $P$ ми маємо з'ясувати, скільки разів рядок $P$ з'являється в рядку $T$ як підрядок.

Ми будуємо суфіксний автомат для тексту $T$.

Далі робимо таку попередню обробку: для кожного стану $v$ в автоматі ми обчислюємо число $cnt[v]$, що дорівнює розміру множини $endpos(v)$. Насправді всі рядки, що відповідають одному й тому самому стану $v$, з'являються в тексті $T$ однакову кількість разів, що дорівнює кількості позицій у множині $endpos$.

Однак ми не можемо будувати множини $endpos$ явно, тому розглядаємо лише їхні розміри $cnt$.

Щоб їх обчислити, ми робимо так. Для кожного стану, якщо його було створено не клонуванням (і якщо це не початковий стан $t_0$), ми ініціалізуємо його значенням $cnt = 1$. Потім ми пройдемося по всіх станах у порядку спадання їхньої довжини $len$ і додамо поточне значення $cnt[v]$ до суфіксних посилань:

$$cnt[link(v)] \text{ += } cnt[v]$$

Це дає правильне значення для кожного стану.

Чому це правильно? Загальна кількість станів, отриманих не через клонування, дорівнює точно $length(T)$, і перші $i$ з них з'явилися, коли ми додали перші $i$ символів. Отже, для кожного з цих станів ми рахуємо відповідну позицію, на якій його було оброблено. Тому спочатку ми маємо $cnt = 1$ для кожного такого стану і $cnt = 0$ для всіх інших.

Потім ми застосовуємо таку операцію для кожного $v$: $cnt[link(v)] \text{ += } cnt[v]$. Сенс цього в тому, що якщо рядок $v$ з'являється $cnt[v]$ разів, то й усі його суфікси з'являються в тих самих кінцевих позиціях, а отже, теж $cnt[v]$ разів.

Чому ми не рахуємо забагато в цій процедурі (тобто не рахуємо деякі позиції двічі)? Бо ми додаємо позиції стану лише до одного іншого стану, тож не може статися, щоб один стан спрямовував свої позиції до іншого стану двічі двома різними способами.

Таким чином, ми можемо обчислити величини $cnt$ для всіх станів автомата за $O(length(T))$ часу.

Після цього відповідь на запит — це просто значення $cnt[t]$, де $t$ — стан, що відповідає взірцю, якщо такий стан існує. Інакше відповідаємо $0$. Відповідь на запит займає $O(length(P))$ часу.

Позиція першого входження

Дано текст $T$ і кілька запитів. Для кожного рядка запиту $P$ ми хочемо знайти позицію першого входження $P$ у рядок $T$ (позицію початку $P$).

Ми знову будуємо суфіксний автомат. Додатково ми попередньо обчислюємо позицію $firstpos$ для всіх станів в автоматі, тобто для кожного стану $v$ ми хочемо знайти позицію $firstpos[v]$ кінця першого входження. Іншими словами, ми хочемо заздалегідь знайти мінімальний елемент кожної множини $endpos$ (оскільки, очевидно, ми не можемо підтримувати всі множини $endpos$ явно).

Щоб підтримувати ці позиції $firstpos$, ми розширюємо функцію sa_extend(). Коли ми створюємо новий стан $cur$, ми покладаємо:

$$firstpos(cur) = len(cur) - 1$$

А коли ми клонуємо вершину $q$ як $clone$, ми покладаємо:

$$firstpos(clone) = firstpos(q)$$

(оскільки єдиний інший варіант значення — це $firstpos(cur)$, який, безперечно, завеликий)

Таким чином, відповідь на запит — це просто $firstpos(t) - length(P) + 1$, де $t$ — стан, що відповідає рядку $P$. Відповідь на запит знову займає лише $O(length(P))$ часу.

Усі позиції входжень

Цього разу нам потрібно вивести всі позиції входжень у рядок $T$.

Знову будуємо суфіксний автомат для тексту $T$. Подібно до попередньої задачі ми обчислюємо позицію $firstpos$ для всіх станів.

Очевидно, $firstpos(t)$ є частиною відповіді, якщо $t$ — стан, що відповідає рядку запиту $P$. Отже, ми врахували стан автомата, що містить $P$. Які ще стани нам потрібно врахувати? Усі стани, що відповідають рядкам, для яких $P$ є суфіксом. Іншими словами, нам потрібно знайти всі стани, з яких можна досягти стану $t$ через суфіксні посилання.

Тому для розв'язання задачі нам потрібно зберігати для кожного стану список суфіксних посилань, що ведуть до нього. Тоді відповідь на запит міститиме всі $firstpos$ для кожного стану, який ми можемо знайти за допомогою DFS / BFS, починаючи зі стану $t$ і користуючись лише суфіксними посиланнями.

Загалом це потребує $O(length (T))$ на попередню обробку і $O(length(P) + answer(P))$ на кожен запит, де $answer(P)$ — це розмір відповіді.

Спочатку ми спускаємося автоматом для кожного символу взірця, щоб знайти наш початковий вузол, що потребує $O(length(P))$. Потім ми застосовуємо наш прийом, який працюватиме за час $O(answer(P))$, бо ми не відвідуватимемо жоден стан двічі (оскільки з кожного стану виходить лише одне суфіксне посилання, тож не може бути двох різних шляхів, що ведуть до того самого стану).

Ми лише маємо врахувати, що два різні стани можуть мати однакове значення $firstpos$. Це трапляється, якщо один стан було отримано клонуванням іншого. Однак це не псує складність, оскільки кожен стан може мати щонайбільше один клон.

Більше того, ми можемо також позбутися повторюваних позицій, якщо не виводитимемо позиції з клонованих станів. Насправді стан, якого може досягти клонований стан, також досяжний з оригінального стану. Тому, якщо ми запам'ятаємо прапорець is_cloned для кожного стану, ми можемо просто ігнорувати клоновані стани й виводити $firstpos$ лише для всіх інших станів.

Ось кілька начерків реалізації:

C++

struct state {
    ...
    bool is_clone;
    int first_pos;
    vector<int> inv_link;
};

// after constructing the automaton
for (int v = 1; v < sz; v++) {
    st[st[v].link].inv_link.push_back(v);
}

// output all positions of occurrences
void output_all_occurrences(int v, int P_length) {
    if (!st[v].is_clone)
        cout << st[v].first_pos - P_length + 1 << endl;
    for (int u : st[v].inv_link)
        output_all_occurrences(u, P_length);
}

Python

class State:
    ...
    is_clone: bool
    first_pos: int
    inv_link: list[int]   # обернені суфіксні посилання

# після побудови автомата
for v in range(1, sz):
    st[st[v].link].inv_link.append(v)

# вивести всі позиції входжень
def output_all_occurrences(v: int, p_length: int):
    if not st[v].is_clone:
        print(st[v].first_pos - p_length + 1)
    for u in st[v].inv_link:
        output_all_occurrences(u, p_length)

TypeScript

interface State {
    // ...
    isClone: boolean;
    firstPos: number;
    invLink: number[];   // обернені суфіксні посилання
}

// після побудови автомата
for (let v = 1; v < sz; v++) {
    st[st[v].link].invLink.push(v);
}

// вивести всі позиції входжень
function outputAllOccurrences(v: number, pLength: number): void {
    if (!st[v].isClone) {
        console.log(st[v].firstPos - pLength + 1);
    }
    for (const u of st[v].invLink) {
        outputAllOccurrences(u, pLength);
    }
}

Go

type state struct {
    // ...
    isClone  bool
    firstPos int
    invLink  []int // обернені суфіксні посилання
}

// після побудови автомата
for v := 1; v < sz; v++ {
    p := st[v].link
    st[p].invLink = append(st[p].invLink, v)
}

// вивести всі позиції входжень
func outputAllOccurrences(v, pLength int) {
    if !st[v].isClone {
        fmt.Println(st[v].firstPos - pLength + 1)
    }
    for _, u := range st[v].invLink {
        outputAllOccurrences(u, pLength)
    }
}

Найкоротший рядок, що не зустрічається

Дано рядок $S$ і певний алфавіт. Нам потрібно знайти рядок найменшої довжини, який не зустрічається в $S$.

Ми застосуємо динамічне програмування на суфіксному автоматі, побудованому для рядка $S$.

Нехай $d[v]$ — відповідь для вузла $v$, тобто ми вже обробили частину підрядка, наразі перебуваємо у стані $v$ і хочемо знайти найменшу кількість символів, які треба додати, щоб знайти неіснуючий перехід. Обчислення $d[v]$ дуже просте. Якщо немає переходу хоча б за одним символом алфавіту, то $d[v] = 1$. Інакше одного символу недостатньо, і тому нам потрібно взяти мінімум з усіх відповідей усіх переходів:

$$d[v] = 1 + \min_{w:(v,w,c) \in SA} d[w].$$

Відповіддю до задачі буде $d[t_0]$, а сам рядок можна відновити за допомогою обчисленого масиву $d[]$.

Найдовший спільний підрядок двох рядків

Дано два рядки $S$ і $T$. Нам потрібно знайти найдовший спільний підрядок, тобто такий рядок $X$, що з'являється як підрядок у $S$ і також у $T$.

Ми будуємо суфіксний автомат для рядка $S$.

Тепер ми візьмемо рядок $T$ і для кожного префікса шукатимемо найдовший суфікс цього префікса в $S$. Іншими словами, для кожної позиції в рядку $T$ ми хочемо знайти найдовший спільний підрядок $S$ і $T$, що закінчується в цій позиції.

Для цього ми використаємо дві змінні — поточний стан $v$ і поточну довжину $l$. Ці дві змінні описуватимуть поточну зіставлену частину: її довжину і стан, що їй відповідає.

Спочатку $v = t_0$ і $l = 0$, тобто зіставлення порожнє.

Тепер опишемо, як ми можемо додати символ $T[i]$ і перерахувати для нього відповідь.

• Якщо з $v$ є перехід за символом $T[i]$, то ми просто йдемо цим переходом і збільшуємо $l$ на один.
• Якщо такого переходу немає, ми маємо скоротити поточну зіставлену частину, що означає необхідність піти суфіксним посиланням: $v = link(v)$. Водночас поточну довжину треба скоротити. Очевидно, нам потрібно покласти $l = len(v)$, оскільки після проходження суфіксним посиланням ми опиняємося у стані, найдовший відповідний рядок якого є підрядком.
• Якщо переходу за потрібним символом усе ще немає, ми повторюємо і знову йдемо суфіксним посиланням і зменшуємо $l$, доки не знайдемо перехід або не досягнемо фіктивного стану $-1$ (що означає, що символ $T[i]$ зовсім не з'являється в $S$, тож ми покладаємо $v = l = 0$).

Відповіддю до задачі буде максимум усіх значень $l$.

Складність цієї частини — $O(length(T))$, оскільки за один крок ми можемо або збільшити $l$ на один, або зробити кілька проходів суфіксними посиланнями, кожен з яких зрештою зменшує значення $l$.

Реалізація:

C++

string lcs (string S, string T) {
    sa_init();
    for (int i = 0; i < S.size(); i++)
        sa_extend(S[i]);
 
    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < T.size(); i++) {
        while (v && !st[v].next.count(T[i])) {
            v = st[v].link ;
            l = st[v].len;
        }
        if (st[v].next.count(T[i])) {
            v = st [v].next[T[i]];
            l++;
        }
        if (l > best) {
            best = l;
            bestpos = i;
        }
    }
    return T.substr(bestpos - best + 1, best);
} 

Python

def lcs(s: str, t: str) -> str:
    sa_init()
    for ch in s:
        sa_extend(ch)

    v = l = best = bestpos = 0
    for i in range(len(t)):
        # доки немає переходу за t[i], спускаємось суфіксним посиланням
        while v and t[i] not in st[v].next:
            v = st[v].link
            l = st[v].len
        if t[i] in st[v].next:
            v = st[v].next[t[i]]
            l += 1
        if l > best:
            best = l
            bestpos = i
    return t[bestpos - best + 1: bestpos + 1]

TypeScript

function lcs(s: string, t: string): string {
    saInit();
    for (const ch of s) {
        saExtend(ch);
    }

    let v = 0, l = 0, best = 0, bestpos = 0;
    for (let i = 0; i < t.length; i++) {
        // доки немає переходу за t[i], спускаємось суфіксним посиланням
        while (v && !st[v].next.has(t[i])) {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.has(t[i])) {
            v = st[v].next.get(t[i])!;
            l++;
        }
        if (l > best) {
            best = l;
            bestpos = i;
        }
    }
    return t.substring(bestpos - best + 1, bestpos + 1);
}

Go

func lcs(s, t string) string {
    saInit()
    for i := 0; i < len(s); i++ {
        saExtend(s[i])
    }

    v, l, best, bestpos := 0, 0, 0, 0
    for i := 0; i < len(t); i++ {
        c := t[i]
        // доки немає переходу за c, спускаємось суфіксним посиланням
        for v != 0 {
            if _, ok := st[v].next[c]; ok {
                break
            }
            v = st[v].link
            l = st[v].length
        }
        if nv, ok := st[v].next[c]; ok {
            v = nv
            l++
        }
        if l > best {
            best = l
            bestpos = i
        }
    }
    return t[bestpos-best+1 : bestpos+1]
}

Найдовший спільний підрядок кількох рядків

Задано $k$ рядків $S_i$. Нам потрібно знайти найдовший спільний підрядок, тобто такий рядок $X$, що з'являється як підрядок у кожному рядку $S_i$.

Ми об'єднуємо всі рядки в один великий рядок $T$, розділяючи рядки спеціальними символами $D_i$ (по одному на кожен рядок):

$$T = S_1 + D_1 + S_2 + D_2 + \dots + S_k + D_k.$$

Потім ми будуємо суфіксний автомат для рядка $T$.

Тепер нам потрібно знайти в машині рядок, який міститься в усіх рядках $S_i$, і це можна зробити за допомогою спеціально доданих символів. Зауважимо, що якщо підрядок входить до деякого рядка $S_j$, то в суфіксному автоматі існує шлях, що починається з цього підрядка, містить символ $D_j$ і не містить інших символів $D_1, \dots, D_{j-1}, D_{j+1}, \dots, D_k$.

Таким чином, нам потрібно обчислити досяжність, яка для кожного стану машини й кожного символу $D_i$ показує, чи існує такий шлях. Це легко обчислити за допомогою DFS чи BFS і динамічного програмування. Після цього відповіддю до задачі буде рядок $longest(v)$ для стану $v$, з якого існували шляхи для всіх спеціальних символів.

Задачі для практики

• CSES - Finding Patterns
• CSES - Counting Patterns
• CSES - String Matching
• CSES - Patterns Positions
• CSES - Distinct Substrings
• CSES - Word Combinations
• CSES - String Distribution
• AtCoder - K-th Substring
• SPOJ - SUBLEX
• Codeforces - Cyclical Quest
• Codeforces - String