Префікс-функція. Алгоритм Кнута–Морріса–Пратта

Означення префікс-функції

Нам дано рядок $s$ довжини $n$. Префікс-функція для цього рядка означається як масив $\pi$ довжини $n$, де $\pi[i]$ — це довжина найдовшого власного префікса підрядка $s[0 \dots i]$, який водночас є суфіксом цього підрядка. Власний префікс рядка — це префікс, який не дорівнює самому рядку. За означенням $\pi[0] = 0$.

Математично означення префікс-функції можна записати так:

$$\pi[i] = \max_ {k = 0 \dots i} \{k : s[0 \dots k-1] = s[i-(k-1) \dots i] \}$$

Наприклад, префікс-функція рядка "abcabcd" дорівнює $[0, 0, 0, 1, 2, 3, 0]$, а префікс-функція рядка "aabaaab" дорівнює $[0, 1, 0, 1, 2, 2, 3]$.

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

• Шукаєте один взірець у тексті (або працюєте з періодами/бордерами одного рядка)? (якщо взірців багато одночасно → Ахо-Корасік)
• Потрібен точний збіг підрядка, а не порівняння довільних підрядків за $O(1)$? (якщо потрібні саме порівняння будь-яких підрядків → Хешування рядків)
• Достатньо лінійних структур, без багатьох запитів про суфікси/підрядки? (якщо потрібні лексикографічні запити на суфіксах → Суфіксний масив)

Тривіальний алгоритм

Алгоритм, який точно слідує означенню префікс-функції, такий:

C++

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 0; i < n; i++)
        for (int k = 0; k <= i; k++)
            if (s.substr(0, k) == s.substr(i-k+1, k))
                pi[i] = k;
    return pi;
}

Python

def prefix_function(s: str) -> list[int]:
    n = len(s)
    pi = [0] * n
    for i in range(n):
        for k in range(i + 1):
            # Порівнюємо префікс довжини k із суфіксом, що закінчується в позиції i
            if s[0:k] == s[i - k + 1:i + 1]:
                pi[i] = k
    return pi

TypeScript

function prefixFunction(s: string): number[] {
  const n = s.length;
  const pi = new Array<number>(n).fill(0);
  for (let i = 0; i < n; i++) {
    for (let k = 0; k <= i; k++) {
      // Порівнюємо префікс довжини k із суфіксом, що закінчується в позиції i
      if (s.slice(0, k) === s.slice(i - k + 1, i + 1)) {
        pi[i] = k;
      }
    }
  }
  return pi;
}

Go

func prefixFunction(s string) []int {
    n := len(s)
    pi := make([]int, n)
    for i := 0; i < n; i++ {
        for k := 0; k <= i; k++ {
            // Порівнюємо префікс довжини k із суфіксом, що закінчується в позиції i
            if s[0:k] == s[i-k+1:i+1] {
                pi[i] = k
            }
        }
    }
    return pi
}

Легко бачити, що його складність становить $O(n^3)$, що залишає простір для покращення.

Ефективний алгоритм

Цей алгоритм запропонували Кнут і Пратт та незалежно від них Морріс у 1977 році. Його використовували як основну функцію алгоритму пошуку підрядка.

Перша оптимізація

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

Справді, інакше, якби $\pi[i + 1] \gt \pi[i] + 1$, то ми могли б узяти цей суфікс, що закінчується в позиції $i + 1$, довжини $\pi[i + 1]$ і прибрати з нього останній символ. Ми отримали б суфікс, що закінчується в позиції $i$, довжини $\pi[i + 1] - 1$, що краще за $\pi[i]$, тобто маємо суперечність.

Наступна ілюстрація показує цю суперечність. Найдовший власний суфікс у позиції $i$, який водночас є префіксом, має довжину $2$, а в позиції $i+1$ — довжину $4$. Тому рядок $s_0 ~ s_1 ~ s_2 ~ s_3$ дорівнює рядку $s_{i-2} ~ s_{i-1} ~ s_i ~ s_{i+1}$, а це означає, що й рядки $s_0 ~ s_1 ~ s_2$ та $s_{i-2} ~ s_{i-1} ~ s_i$ рівні, отже $\pi[i]$ має дорівнювати $3$.

$$\underbrace{\overbrace{s_0 ~ s_1}^{\pi[i] = 2} ~ s_2 ~ s_3}_{\pi[i+1] = 4} ~ \dots ~ \underbrace{s_{i-2} ~ \overbrace{s_{i-1} ~ s_{i}}^{\pi[i] = 2} ~ s_{i+1}}_{\pi[i+1] = 4}$$

Отже, переходячи до наступної позиції, значення префікс-функції може або зрости на одиницю, або лишитися тим самим, або зменшитися на якусь величину. Цей факт уже дозволяє нам знизити складність алгоритму до $O(n^2)$, бо за один крок префікс-функція може зрости щонайбільше на одиницю. Загалом функція може зрости щонайбільше $n$ кроків, а отже й зменшитися загалом теж щонайбільше $n$ кроків. Це означає, що нам потрібно виконати лише $O(n)$ порівнянь рядків, і ми досягаємо складності $O(n^2)$.

Друга оптимізація

Підемо далі — ми хочемо позбутися порівнянь рядків. Щоб цього досягти, нам треба використати всю інформацію, обчислену на попередніх кроках.

Отже, обчислимо значення префікс-функції $\pi$ для $i + 1$. Якщо $s[i+1] = s[\pi[i]]$, то ми можемо з упевненістю сказати, що $\pi[i+1] = \pi[i] + 1$, оскільки ми вже знаємо, що суфікс у позиції $i$ довжини $\pi[i]$ дорівнює префіксу довжини $\pi[i]$. Це знову проілюстровано на прикладі.

$$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}_{\pi[i+1] = \pi[i] + 1} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i]} ~ \overbrace{s_{i+1}}^{s_3 = s_{i + 1}}}_{\pi[i+1] = \pi[i] + 1}$$

Якщо ж це не так, $s[i+1] \neq s[\pi[i]]$, то нам потрібно спробувати коротший рядок. Щоб пришвидшити справу, ми хотіли б одразу перейти до найбільшої довжини $j \lt \pi[i]$ такої, що в позиції $i$ виконується префіксна властивість, тобто $s[0 \dots j-1] = s[i-j+1 \dots i]$:

$$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$$

Справді, якщо ми знайдемо таку довжину $j$, то нам знову потрібно лише порівняти символи $s[i+1]$ та $s[j]$. Якщо вони рівні, то ми можемо присвоїти $\pi[i+1] = j + 1$. Інакше нам потрібно буде знайти найбільше значення, менше за $j$, для якого виконується префіксна властивість, і так далі. Може статися, що це триватиме до $j = 0$. Якщо тоді $s[i+1] = s[0]$, ми присвоюємо $\pi[i+1] = 1$, а інакше $\pi[i+1] = 0$.

Отже, у нас уже є загальна схема алгоритму. Лишається єдине запитання — як ефективно знаходити довжини для $j$. Підсумуймо: для поточної довжини $j$ у позиції $i$, для якої виконується префіксна властивість, тобто $s[0 \dots j-1] = s[i-j+1 \dots i]$, ми хочемо знайти найбільше $k \lt j$, для якого виконується префіксна властивість.

$$\overbrace{\underbrace{s_0 ~ s_1}_k ~ s_2 ~ s_3}^j ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_k}^j ~s_{i+1}$$

Ілюстрація показує, що це має бути значення $\pi[j-1]$, яке ми вже обчислили раніше.

Остаточний алгоритм

Отже, ми нарешті можемо побудувати алгоритм, який не виконує жодних порівнянь рядків і виконує лише $O(n)$ дій.

Ось остаточна процедура:

• Ми обчислюємо значення префікс-функції $\pi[i]$ у циклі, ітеруючи від $i = 1$ до $i = n-1$ (значенню $\pi[0]$ просто присвоюємо $0$).
• Щоб обчислити поточне значення $\pi[i]$, ми задаємо змінну $j$, що позначає довжину найкращого суфікса для $i-1$. Спочатку $j = \pi[i-1]$.
• Перевіряємо, чи суфікс довжини $j+1$ є також і префіксом, порівнюючи $s[j]$ і $s[i]$. Якщо вони рівні, то присвоюємо $\pi[i] = j + 1$, інакше зменшуємо $j$ до $\pi[j-1]$ і повторюємо цей крок.
• Якщо ми досягли довжини $j = 0$ і досі не маємо збігу, то присвоюємо $\pi[i] = 0$ і переходимо до наступного індексу $i + 1$.

Реалізація

Реалізація виявляється напрочуд короткою та виразною.

C++

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

Python

def prefix_function(s: str) -> list[int]:
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        # Відкочуємося за значеннями префікс-функції, доки не знайдемо збіг
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

TypeScript

function prefixFunction(s: string): number[] {
  const n = s.length;
  const pi = new Array<number>(n).fill(0);
  for (let i = 1; i < n; i++) {
    let j = pi[i - 1];
    // Відкочуємося за значеннями префікс-функції, доки не знайдемо збіг
    while (j > 0 && s[i] !== s[j]) {
      j = pi[j - 1];
    }
    if (s[i] === s[j]) {
      j++;
    }
    pi[i] = j;
  }
  return pi;
}

Go

func prefixFunction(s string) []int {
    n := len(s)
    pi := make([]int, n)
    for i := 1; i < n; i++ {
        j := pi[i-1]
        // Відкочуємося за значеннями префікс-функції, доки не знайдемо збіг
        for j > 0 && s[i] != s[j] {
            j = pi[j-1]
        }
        if s[i] == s[j] {
            j++
        }
        pi[i] = j
    }
    return pi
}

Це онлайн-алгоритм, тобто він обробляє дані в міру їх надходження — наприклад, можна читати символи рядка по одному й одразу їх обробляти, знаходячи значення префікс-функції для кожного наступного символу. Алгоритм усе ще потребує зберігання самого рядка та раніше обчислених значень префікс-функції, але якщо ми наперед знаємо максимальне значення $M$, яке префікс-функція може набути на рядку, то ми можемо зберігати лише $M+1$ перших символів рядка та таку саму кількість значень префікс-функції.

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

Пошук підрядка в рядку. Алгоритм Кнута–Морріса–Пратта

Це задача є класичним застосуванням префікс-функції.

Дано текст $t$ і рядок $s$, ми хочемо знайти та вивести позиції всіх входжень рядка $s$ у текст $t$.

Для зручності позначимо через $n$ довжину рядка $s$, а через $m$ — довжину тексту $t$.

Ми утворюємо рядок $s + \# + t$, де $\#$ — це роздільник, який не зустрічається ані в $s$, ані в $t$. Обчислимо префікс-функцію для цього рядка. Тепер подумаймо про значення префікс-функції, крім перших $n + 1$ елементів (які належать рядку $s$ і роздільнику). За означенням значення $\pi[i]$ показує найбільшу довжину підрядка, що закінчується в позиції $i$, який збігається з префіксом. Але в нашому випадку це не що інше, як найбільший блок, що збігається з $s$ і закінчується в позиції $i$. Ця довжина не може бути більшою за $n$ через роздільник. Але якщо досягається рівність $\pi[i] = n$, то це означає, що рядок $s$ повністю з’являється в цій позиції, тобто закінчується в позиції $i$. Тільки не забуваймо, що позиції індексуються в рядку $s + \# + t$.

Отже, якщо в якійсь позиції $i$ ми маємо $\pi[i] = n$, то в позиції $i - (n + 1) - n + 1 = i - 2n$ у рядку $t$ з’являється рядок $s$.

Як уже згадувалося в описі обчислення префікс-функції, якщо ми знаємо, що значення префікса ніколи не перевищують певного значення, то нам не потрібно зберігати весь рядок і всю функцію, а лише її початок. У нашому випадку це означає, що нам потрібно зберігати лише рядок $s + \#$ і значення префікс-функції для нього. Ми можемо читати рядок $t$ по одному символу за раз і обчислювати поточне значення префікс-функції.

Отже, алгоритм Кнута–Морріса–Пратта розв’язує задачу за час $O(n + m)$ і пам’ять $O(n)$.

Підрахунок кількості входжень кожного префікса

Тут ми обговорюємо одразу дві задачі. Дано рядок $s$ довжини $n$. У першому варіанті задачі ми хочемо підрахувати кількість появ кожного префікса $s[0 \dots i]$ у тому самому рядку. У другому варіанті задачі дано інший рядок $t$, і ми хочемо підрахувати кількість появ кожного префікса $s[0 \dots i]$ у $t$.

Спочатку розв’яжемо першу задачу. Розгляньмо значення префікс-функції $\pi[i]$ у позиції $i$. За означенням це означає, що префікс довжини $\pi[i]$ рядка $s$ зустрічається й закінчується в позиції $i$, і немає довшого префікса, який задовольняв би це означення. Водночас коротші префікси можуть закінчуватися в цій позиції. Неважко бачити, що ми маємо те саме запитання, на яке ми вже відповіли, коли обчислювали саму префікс-функцію: дано префікс довжини $j$, який є суфіксом, що закінчується в позиції $i$, — який наступний менший префікс $\lt j$, що теж є суфіксом, який закінчується в позиції $i$. Отже, у позиції $i$ закінчується префікс довжини $\pi[i]$, префікс довжини $\pi[\pi[i] - 1]$, префікс $\pi[\pi[\pi[i] - 1] - 1]$, і так далі, доки індекс не стане нулем. Отже, ми можемо обчислити відповідь у такий спосіб.

C++

vector<int> ans(n + 1);
for (int i = 0; i < n; i++)
    ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
    ans[pi[i-1]] += ans[i];
for (int i = 0; i <= n; i++)
    ans[i]++;

Python

ans = [0] * (n + 1)
for i in range(n):
    ans[pi[i]] += 1
for i in range(n - 1, 0, -1):
    ans[pi[i - 1]] += ans[i]
for i in range(n + 1):
    ans[i] += 1

TypeScript

const ans = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) {
  ans[pi[i]]++;
}
for (let i = n - 1; i > 0; i--) {
  ans[pi[i - 1]] += ans[i];
}
for (let i = 0; i <= n; i++) {
  ans[i]++;
}

Go

ans := make([]int, n+1)
for i := 0; i < n; i++ {
    ans[pi[i]]++
}
for i := n - 1; i > 0; i-- {
    ans[pi[i-1]] += ans[i]
}
for i := 0; i <= n; i++ {
    ans[i]++
}

Тут для кожного значення префікс-функції ми спочатку рахуємо, скільки разів воно зустрічається в масиві $\pi$, а потім обчислюємо остаточні відповіді: якщо ми знаємо, що префікс довжини $i$ з’являється рівно $\text{ans}[i]$ разів, то це число треба додати до кількості входжень його найдовшого суфікса, який водночас є префіксом. Наприкінці нам потрібно додати $1$ до кожного результату, оскільки нам потрібно врахувати й самі вихідні префікси.

Тепер розгляньмо другу задачу. Ми застосовуємо трюк з алгоритму Кнута–Морріса–Пратта: ми утворюємо рядок $s + \# + t$ і обчислюємо його префікс-функцію. Єдина відмінність від першої задачі полягає в тому, що нас цікавлять лише значення префікса, які стосуються рядка $t$, тобто $\pi[i]$ для $i \ge n + 1$. З цими значеннями ми можемо виконати точно такі самі обчислення, як у першій задачі.

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

Дано рядок $s$ довжини $n$. Ми хочемо обчислити кількість різних підрядків, що в ньому зустрічаються.

Ми розв’язуватимемо цю задачу ітеративно. А саме, ми навчимося, знаючи поточну кількість різних підрядків, перераховувати цю кількість, додаючи символ у кінець.

Отже, нехай $k$ — це поточна кількість різних підрядків у $s$, і ми додаємо символ $c$ у кінець $s$. Очевидно, що з’являться деякі нові підрядки, які закінчуються на $c$. Ми хочемо підрахувати ці нові підрядки, яких не було раніше.

Ми беремо рядок $t = s + c$ і обертаємо його. Тепер задача перетворюється на обчислення того, скільки є префіксів, які більше ніде не зустрічаються. Якщо ми обчислимо максимальне значення префікс-функції $\pi_{\text{max}}$ оберненого рядка $t$, то найдовший префікс, який зустрічається в $s$, має довжину $\pi_{\text{max}}$. Зрозуміло, що в ньому також зустрічаються всі префікси меншої довжини.

Тому кількість нових підрядків, що з’являються, коли ми додаємо новий символ $c$, дорівнює $|s| + 1 - \pi_{\text{max}}$.

Отже, для кожного доданого символу ми можемо обчислити кількість нових підрядків за час $O(n)$, що дає часову складність $O(n^2)$ загалом.

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

Стиснення рядка

Дано рядок $s$ довжини $n$. Ми хочемо знайти найкоротше «стиснуте» подання рядка, тобто ми хочемо знайти рядок $t$ найменшої довжини такий, що $s$ можна подати як конкатенацію однієї або кількох копій $t$.

Зрозуміло, що нам потрібно знайти лише довжину $t$. Знаючи довжину, відповіддю до задачі буде префікс $s$ цієї довжини.

Обчислимо префікс-функцію для $s$. Використовуючи її останнє значення, ми визначаємо величину $k = n - \pi[n - 1]$. Ми покажемо, що якщо $k$ ділить $n$, то $k$ буде відповіддю, інакше ефективного стиснення не існує, і відповідь — це $n$.

Нехай $n$ ділиться на $k$. Тоді рядок можна розбити на блоки довжини $k$. За означенням префікс-функції префікс довжини $n - k$ дорівнюватиме своєму суфіксу. Але це означає, що останній блок дорівнює блоку перед ним. А блок перед ним має дорівнювати блоку перед ним. І так далі. У результаті виявляється, що всі блоки рівні, отже, ми можемо стиснути рядок $s$ до довжини $k$.

Звісно, нам ще потрібно показати, що це справді оптимум. Справді, якби існувало стиснення менше за $k$, то префікс-функція в кінці була б більшою за $n - k$. Тому $k$ справді є відповіддю.

Тепер припустімо, що $n$ не ділиться на $k$. Ми покажемо, що це означає, що довжина відповіді дорівнює $n$. Доведемо це від супротивного. Припустимо, що відповідь існує, і стиснення має довжину $p$ ($p$ ділить $n$). Тоді останнє значення префікс-функції має бути більшим за $n - p$, тобто суфікс частково накриватиме перший блок. Тепер розгляньмо другий блок рядка. Оскільки префікс дорівнює суфіксу, і обидва — і префікс, і суфікс — накривають цей блок, а їхнє зміщення одне відносно одного $k$ не ділить довжину блоку $p$ (інакше $k$ ділило б $n$), то всі символи блоку мають бути однаковими. Але тоді рядок складається лише з одного символу, повтореного знову і знову, отже, ми можемо стиснути його до рядка розміру $1$, що дає $k = 1$, і $k$ ділить $n$. Суперечність.

$$\overbrace{s_0 ~ s_1 ~ s_2 ~ s_3}^p ~ \overbrace{s_4 ~ s_5 ~ s_6 ~ s_7}^p$$ $$s_0 ~ s_1 ~ s_2 ~ \underbrace{\overbrace{s_3 ~ s_4 ~ s_5 ~ s_6}^p ~ s_7}_{\pi[7] = 5}$$ $$s_4 = s_3, ~ s_5 = s_4, ~ s_6 = s_5, ~ s_7 = s_6 ~ \Rightarrow ~ s_0 = s_1 = s_2 = s_3$$

Побудова автомата за префікс-функцією

Повернімося до конкатенації двох рядків через роздільник, тобто для рядків $s$ і $t$ ми обчислюємо префікс-функцію рядка $s + \# + t$. Очевидно, оскільки $\#$ — це роздільник, значення префікс-функції ніколи не перевищить $|s|$. Звідси випливає, що достатньо зберігати лише рядок $s + \#$ і значення префікс-функції для нього, а префікс-функцію для всіх наступних символів ми можемо обчислювати на льоту:

$$\underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{need to store}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{do not need to store}}$$

Справді, у такій ситуації, знаючи наступний символ $c \in t$ і значення префікс-функції попередньої позиції, ми маємо достатньо інформації, щоб обчислити наступне значення префікс-функції, не використовуючи жодних попередніх символів рядка $t$ і значень префікс-функції в них.

Іншими словами, ми можемо побудувати автомат (скінченний автомат): станом у ньому є поточне значення префікс-функції, а перехід з одного стану в інший виконуватиметься через наступний символ.

Отже, навіть не маючи рядка $t$, ми можемо побудувати таку таблицю переходів $(\text{old}_\pi, c) \rightarrow \text{new}_\pi$, використовуючи той самий алгоритм, що й для обчислення таблиці переходів:

C++

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int j = i;
            while (j > 0 && 'a' + c != s[j])
                j = pi[j-1];
            if ('a' + c == s[j])
                j++;
            aut[i][c] = j;
        }
    }
}

Python

def compute_automaton(s: str) -> list[list[int]]:
    s += "#"
    n = len(s)
    pi = prefix_function(s)
    aut = [[0] * 26 for _ in range(n)]
    for i in range(n):
        for c in range(26):
            j = i
            # Символ алфавіту 'a' + c подаємо кодом
            while j > 0 and ord("a") + c != ord(s[j]):
                j = pi[j - 1]
            if ord("a") + c == ord(s[j]):
                j += 1
            aut[i][c] = j
    return aut

TypeScript

function computeAutomaton(s: string): number[][] {
  s += "#";
  const n = s.length;
  const pi = prefixFunction(s);
  const aut: number[][] = Array.from({ length: n }, () => new Array<number>(26).fill(0));
  const a = "a".charCodeAt(0);
  for (let i = 0; i < n; i++) {
    for (let c = 0; c < 26; c++) {
      let j = i;
      // Символ алфавіту 'a' + c подаємо кодом
      while (j > 0 && a + c !== s.charCodeAt(j)) {
        j = pi[j - 1];
      }
      if (a + c === s.charCodeAt(j)) {
        j++;
      }
      aut[i][c] = j;
    }
  }
  return aut;
}

Go

func computeAutomaton(s string) [][]int {
    s += "#"
    n := len(s)
    pi := prefixFunction(s)
    aut := make([][]int, n)
    for i := range aut {
        aut[i] = make([]int, 26)
    }
    for i := 0; i < n; i++ {
        for c := 0; c < 26; c++ {
            j := i
            // Символ алфавіту 'a' + c подаємо кодом
            for j > 0 && byte('a')+byte(c) != s[j] {
                j = pi[j-1]
            }
            if byte('a')+byte(c) == s[j] {
                j++
            }
            aut[i][c] = j
        }
    }
    return aut
}

Однак у такій формі алгоритм працює за час $O(n^2 26)$ для малих літер алфавіту. Зауважимо, що ми можемо застосувати динамічне програмування й використати вже обчислені частини таблиці. Щоразу, коли ми переходимо від значення $j$ до значення $\pi[j-1]$, ми насправді маємо на увазі, що перехід $(j, c)$ веде до того самого стану, що й перехід $(\pi[j-1], c)$, а ця відповідь уже точно обчислена.

C++

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[pi[i-1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
        }
    }
}

Python

def compute_automaton(s: str) -> list[list[int]]:
    s += "#"
    n = len(s)
    pi = prefix_function(s)
    aut = [[0] * 26 for _ in range(n)]
    for i in range(n):
        for c in range(26):
            ch = ord("a") + c
            if i > 0 and ch != ord(s[i]):
                # Перевикористовуємо вже обчислений рядок таблиці
                aut[i][c] = aut[pi[i - 1]][c]
            else:
                aut[i][c] = i + (1 if ch == ord(s[i]) else 0)
    return aut

TypeScript

function computeAutomaton(s: string): number[][] {
  s += "#";
  const n = s.length;
  const pi = prefixFunction(s);
  const aut: number[][] = Array.from({ length: n }, () => new Array<number>(26).fill(0));
  const a = "a".charCodeAt(0);
  for (let i = 0; i < n; i++) {
    for (let c = 0; c < 26; c++) {
      const ch = a + c;
      if (i > 0 && ch !== s.charCodeAt(i)) {
        // Перевикористовуємо вже обчислений рядок таблиці
        aut[i][c] = aut[pi[i - 1]][c];
      } else {
        aut[i][c] = i + (ch === s.charCodeAt(i) ? 1 : 0);
      }
    }
  }
  return aut;
}

Go

func computeAutomaton(s string) [][]int {
    s += "#"
    n := len(s)
    pi := prefixFunction(s)
    aut := make([][]int, n)
    for i := range aut {
        aut[i] = make([]int, 26)
    }
    for i := 0; i < n; i++ {
        for c := 0; c < 26; c++ {
            ch := byte('a') + byte(c)
            if i > 0 && ch != s[i] {
                // Перевикористовуємо вже обчислений рядок таблиці
                aut[i][c] = aut[pi[i-1]][c]
            } else {
                match := 0
                if ch == s[i] {
                    match = 1
                }
                aut[i][c] = i + match
            }
        }
    }
    return aut
}

У результаті ми будуємо автомат за час $O(26 n)$.

Коли такий автомат корисний? Для початку згадаймо, що ми використовуємо префікс-функцію для рядка $s + \# + t$ і її значення переважно з єдиною метою: знайти всі входження рядка $s$ у рядок $t$.

Тому найочевидніша користь цього автомата — це пришвидшення обчислення префікс-функції для рядка $s + \# + t$. Побудувавши автомат для $s + \#$, нам більше не потрібно зберігати рядок $s$ чи значення префікс-функції в ньому. Усі переходи вже обчислені в таблиці.

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

Для повноти ми розв’яжемо таку задачу: дано число $k \le 10^5$ і рядок $s$ довжини $\le 10^5$. Нам потрібно обчислити кількість входжень $s$ у $k$-й рядок Грея. Нагадаймо, що рядки Грея означаються так:

$$\begin{align} g_1 &= \text{"a"}\\ g_2 &= \text{"aba"}\\ g_3 &= \text{"abacaba"}\\ g_4 &= \text{"abacabadabacaba"} \end{align}$$

У таких випадках навіть побудувати рядок $t$ буде неможливо через його астрономічну довжину. $k$-й рядок Грея має довжину $2^k-1$ символів. Однак ми можемо ефективно обчислити значення префікс-функції в кінці рядка, знаючи лише значення префікс-функції на початку.

Окрім самого автомата, ми також обчислюємо значення $G[i][j]$ — значення автомата після обробки рядка $g_i$, починаючи зі стану $j$. А додатково ми обчислюємо значення $K[i][j]$ — кількість входжень $s$ у $g_i$ під час обробки $g_i$, починаючи зі стану $j$. Власне, $K[i][j]$ — це кількість разів, коли префікс-функція набула значення $|s|$ під час виконання операцій. Відповіддю до задачі тоді буде $K[k][0]$.

Як ми можемо обчислити ці значення? Спочатку базові значення такі: $G[0][j] = j$ і $K[0][j] = 0$. А всі наступні значення можна обчислити з попередніх значень, використовуючи автомат. Щоб обчислити значення для деякого $i$, згадаймо, що рядок $g_i$ складається з $g_{i-1}$, $i$-го символу алфавіту та $g_{i-1}$. Отже, автомат перейде у стан:

$$\text{mid} = \text{aut}[G[i-1][j]][i]$$ $$G[i][j] = G[i-1][\text{mid}]$$

Значення для $K[i][j]$ також легко підрахувати.

$$K[i][j] = K[i-1][j] + (\text{mid} == |s|) + K[i-1][\text{mid}]$$

Отже, ми можемо розв’язати задачу для рядків Грея, а так само й величезну кількість інших подібних задач. Наприклад, точно той самий метод також розв’язує таку задачу: нам дано рядок $s$ і деякі взірці $t_i$, кожен з яких задається так: це рядок зі звичайних символів, і там можуть бути деякі рекурсивні вставки попередніх рядків виду $t_k^{\text{cnt}}$, що означає, що в цьому місці ми маємо вставити рядок $t_k$ $\text{cnt}$ разів. Приклад таких взірців:

$$\begin{align} t_1 &= \text{"abdeca"}\\ t_2 &= \text{"abc"} + t_1^{30} + \text{"abd"}\\ t_3 &= t_2^{50} + t_1^{100}\\ t_4 &= t_2^{10} + t_3^{100} \end{align}$$

Рекурсивні підстановки роздувають рядок так, що їхні довжини можуть сягати порядку $100^{100}$.

Нам потрібно знайти кількість разів, коли рядок $s$ з’являється в кожному з рядків.

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

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

• UVA # 455 "Periodic Strings"
• UVA # 11022 "String Factoring"
• UVA # 11452 "Dancing the Cheeky-Cheeky"
• UVA 12604 - Caesar Cipher
• UVA 12467 - Secret Word
• UVA 11019 - Matrix Matcher
• SPOJ - Pattern Find
• SPOJ - A Needle in the Haystack
• Codeforces - Anthem of Berland
• Codeforces - MUH and Cube Walls
• Codeforces - Prefixes and Suffixes

Відеоматеріали