Префікс-функція

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

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

$$\pi[i] = \max(0, \max_{k=1 \ldots i} ~ \{ ~ k ~ : ~ s[0 \ldots k-1] = s[i-k+1 \ldots i] ~ \}).$$

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

• У рядку "a" немає префікса, який збігається з власним суфіксом.
• У рядку "ab" немає префікса, який збігається з власним суфіксом.
• У рядку "abc" немає префікса, який збігається з власним суфіксом.
• У рядку "abca" префікс довжини $1$ збігається з власним суфіксом.
• У рядку "abcab" префікс довжини $2$ збігається з власним суфіксом.
• У рядку "abcabc" префікс довжини $3$ збігається з власним суфіксом.
• У рядку "abcabcd" немає префікса, який збігається з власним суфіксом.

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

Алгоритм

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

Ефективний алгоритм був розроблений Кнутом (Knuth) та Праттом (Pratt), а також незалежно від них Моррісом (Morris) у 1977 році як основна частина алгоритму пошуку підрядка в рядку.

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

Перше важливе зауваження - значення $\pi[i+1]$ не перевищує значення $\pi[i]$ більше ніж на одиницю для будь-якого $i$.

Доведення. В іншому випадку, якщо $\pi[i+1] > \pi[i] + 1$, то розглянемо суфікс, який закінчується в позиції $i+1$ і має довжину $\pi[i+1]$. Видаливши з нього останній символ, ми отримаємо суфікс, який закінчується в позиції $i$ і має довжину $\pi[i+1]-1$. Це краще, ніж $\pi[i]$, тому ми дійшли до протиріччя. Ілюстрація цього протиріччя (у цьому прикладі $\pi[i-1]$ має бути рівне 3):

$$\underbrace{ \overbrace{s_0 \ s_1}^{\pi[i-1]=2} \ s_2 \ s_3}_{\pi[i]=4} \ \ldots\ \underbrace{ s_{i-3}\ \overbrace{s_{i-2}\ s_{i-1}}^{\pi[i-1]=2} \ s_i}_{\pi[i]=4}$$

На цій схемі верхні фігурні дужки позначають два однакові підрядки довжиною 2, а нижні фігурні дужки - два однакові підрядки довжиною 4.

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

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

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

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

$$\underbrace{ \overbrace{s_0 \ s_1 \ s_2}^{\pi[i]} \ \overbrace{s_3}^{s_3=s_{i+1}}}_{\pi[i+1]=\pi[i]+1} \ \ldots\ \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] \ne s[\pi[i]]$. Це означає, що нам потрібно спробувати підрядок меншої довжини. З метою оптимізації бажано одразу перейти до такої найбільшої довжини $j < \pi[i]$, що, як і раніше, виконується префікс-властивість в позиції $i$, тобто $s[0 \ldots j-1] = s[i-j+1 \ldots i]$.

$$\overbrace{\underbrace{s_0 \ s_1}_{j} \ s_2 \ s_3}^{\pi[i]} \ \ldots\ \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$ закінчаться - це трапляється, коли $j=0$. У цьому випадку, якщо $s[i+1]=s[0]$, то $\pi[i+1]=1$, інакше $\pi[i+1]=0$.

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

$$\overbrace{\underbrace{s_0 \ s_1}_{k} \ s_2 \ s_3}^{j} \ \ldots\ \overbrace{ s_{i-3}\ s_{i-2} \underbrace{s_{i-1}\ s_{i}}_{k}}^{j} \ s_{i+1}$$

Значення $k$ є ніщо інше, як значення префікс-функції $\pi[j-1]$, яке ми вже обчислювали раніше (віднімання одиниці зумовлене 0-індексацією рядка). Таким чином, ці довжини $k$ можна знайти за $O(1)$ кожну.

Кінцевий алгоритм

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

Наведемо тут схему алгоритму:

• Значення префікс-функції $\pi[i]$ будемо визначати по черзі: від $i=1$ до $i=n-1$ (значення $\pi[0]$ дорівнює нулю).

• Для підрахунку поточного значення $\pi[i]$ ми заводимо змінну $j$, що позначає довжину поточного розглянутого зразка. Спочатку $j = \pi[i-1]$.

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

• Якщо ми дійшли до довжини $j=0$ і так і не знайшли збігів, то зупиняємо процес перебору зразків, вважаємо $\pi[i] = 0$ і переходимо до наступного індексу $i+1$.

Реалізація

Повільне обчислення за $O(n^3)$

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

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

Обчислення алгоритмом Кнута-Морріса-Пратта за $O(n)$

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;
}

Зауваження

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

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

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

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

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

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

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];
}

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

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

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

Дано рядок $s$ довжини $n$. Потрібно порахувати кількість різних підрядків.

Будемо розв'язувати цю задачу ітеративно. Зокрема, навчимося, знаючи поточну кількість різних підрядків, перераховувати цю кількість при додаванні в кінець одного символу.

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

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

Отже, ми отримали, що кількість нових підрядків, які з'являються при додаванні символу $c$, дорівнює $s.\operatorname{length}() + 1 - \pi_{\max}$.

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

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

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

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

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

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

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

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

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

$$\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\ \ \ \ \Longrightarrow\ \ \ \ s_0=s_1=s_2=s_3$$

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

Повернемося до вже неодноразово використовуваного прийому конкатенації двох рядків через роздільник, тобто для даних рядків $s$ і $t$ обчислення префікс-функції для рядка $s+\#+t$. Очевидно, що якщо символ $\#$ є роздільником, то значення префікс-функції ніколи не перевищить $s.{\rm length}()$. Звідси випливає, що, як згадувалося при описі алгоритму обчислення префікс-функції, достатньо зберігати тільки рядок $s+\#$ і значення префікс-функції для нього, а для всіх наступних символів префікс-функцію обчислювати на льоту

$$\underbrace{s_0\ s_1\ \ldots\ s_{n-1}\ \#}_{\rm need\ to\ save} \underbrace{t_0\ t_1\ \ldots\ t_{m-1}}_{\rm need\ not\ to\ save}$$

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

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

$$s_0\ s_1\ \ldots\ s_{n-1}\ \# \underbrace{\ldots}_{\pi[i-1]}\ \ \Longrightarrow\ \ s_0\ s_1\ \ldots\ s_{n-1}\ \# \underbrace{\ldots}_{\pi[i-1]} + t_i\ \ \Longrightarrow\ \ s_0\ s_1\ \ldots\ s_{n-1}\ \# \ldots \underbrace{t_i}_{\pi[i]}$$

Таким чином, навіть якщо ми ще не маємо рядка $t$, ми можемо попередньо побудувати таблицю переходів $({\rm стара}\_\pi,c) \rightarrow {\rm нова}\_\pi$ за допомогою того ж алгоритму обчислення префікс-функції:

вхідний рядок "s"
константа "alphabet" має значення 256, що відповідає потужності алфавіту символів. Зазвичай вона менша

s += '#';

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

Правда, в такому вигляді алгоритм буде працювати за $O(nk^2)$ ($k$ - потужність алфавіту). Але зауважимо, що замість внутрішнього циклу $\rm while$, який поступово скорочує відповідь, ми можемо скористатися вже обчисленою частиною таблиці: переходячи від значення $j$ до значення $\pi[j-1]$, ми фактично говоримо, що перехід зі стану $(j, c)$ приведе в той же стан, що і перехід $(\pi[j-1], c)$, а для нього відповідь вже точно порахована (тобто $\pi[j-1] < j$):

вхідний рядок "s"
константа "alphabet" має значення 256, що відповідає потужності алфавіту символів. Зазвичай це значення менше

s += '#';

int n = (int)s.length();
vector<int> pi = prefix_function(s);
vector<vector<int>> aut(n, vector<int>(alphabet));
for (int i = 0; i < n; ++i) {
    for (char c = 0; c < alphabet; ++c) {
        if (i > 0 && c != s[i]) {
            aut[i][c] = aut[pi[i - 1]][c];
        } else {
            aut[i][c] = i + (c == s[i]);
        }
    }
}

В результаті вийшла дуже проста реалізація побудови автомата, яка працює за $O(n k)$.

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

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

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

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

$$g_1 = "a"$$

$$g_2 = "aba"$$

$$g_3 = "abacaba"$$

$$g_4 = "abacabadabacaba"$$

$$\ldots$$

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

Отже, крім самого автомата, також порахуємо такі величини: $G[i][j]$ - значення автомата, досягнуте після "годування" йому рядка $g_i$, якщо до цього автомат перебував у стані $j$. Друга величина - $K[i][j]$ - кількість входжень рядка $s$ в рядок $g_i$, якщо до "годування" цього рядка $g_i$ автомат перебував у стані $j$. Фактично, $K[i][j]$ - це кількість разів, коли автомат приймав значення $s.{\rm length}()$ під час "годування" рядка $g_i$. Зрозуміло, що відповіддю на задачу буде величина $K[k][0]$.

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

$${\rm mid} = {\rm aut}[\ G[i-1][j]\ ][{\rm char}_i]$$

Після цього автомату "подаватиметься" останній шматок, тобто $g_{i-1}$

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

Кількості $K[i][j]$ легко визначаються як сума кількостей по трьох частинах $g_i$: рядок $g_{i-1}$, символ ${\rm char}_i$, і знову рядок $g_{i-1}$:

$$K[i][j] = K[i-1][j] + ({\rm mid} == s.{\rm length}()) + K[i-1][mid]$$

Отже, ми вирішили задачу для стрічок Грея. Аналогічно можна розв'язати цілий клас подібних задач. Наприклад, точно таким же методом можна вирішити наступну задачу: дано рядок $s$ і зразки $t_i$, кожен з яких задається наступним чином: це рядок зі звичайних символів, серед яких можуть зустрічатися рекурсивні вставки інших рядків у формі $t_k[\rm cnt]$, яка означає, що в це місце має бути вставлено $\rm cnt$ екземплярів рядка $t_k$. Один з прикладів такої схеми:

$$t_1 = "abdeca"$$

$$t_2 = "abc" + t_1[30] + "abd"$$

$$t_3 = t_2[50] + t_1[100]$$

$$t_4 = t_2[10] + t_3[100]$$

Гарантується, що цей опис не містить циклічних залежностей. Обмеження полягають у тому, що якщо явно розкривати рекурсію і знаходити рядки $t_i$, то їх довжини можуть досягати порядку $100^{100}$.

Потрібно знайти кількість входжень рядка $s$ в кожен з рядків $t_i$.

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

Задачі

Список задач, які можна розв'язати, використовуючи префіксну функцію:

• Online Judge - 455 - "Periodic Strings"

• Online Judge - 11022 - "String Factoring"

• Online Judge - 11452 - "Dancing the Cheeky-Cheeky"