Алгоритм Манакера — пошук усіх підпаліндромів за $O(N)$

Постановка задачі

Дано рядок $s$ довжини $n$. Знайти всі пари $(i, j)$ такі, що підрядок $s[i\dots j]$ є паліндромом. Рядок $t$ є паліндромом, коли $t = t_{rev}$ ($t_{rev}$ — це обернений рядок до $t$).

Точніше формулювання

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

Але інформацію про паліндроми можна зберігати компактно: для кожної позиції $i$ ми знайдемо кількість непорожніх паліндромів із центром у цій позиції.

Паліндроми зі спільним центром утворюють неперервний ланцюжок: якщо ми маємо паліндром довжини $l$ із центром у $i$, то ми також маємо паліндроми довжин $l-2$, $l-4$ і так далі, теж із центром у $i$. Тому ми збираємо інформацію про всі паліндромні підрядки саме в такий спосіб.

Паліндроми непарної та парної довжини враховуються окремо як $d_{odd}[i]$ і $d_{even}[i]$. Для паліндромів парної довжини ми вважаємо, що вони мають центр у позиції $i$, якщо їхні два центральні символи — це $s[i]$ і $s[i-1]$.

Наприклад, рядок $s = abababc$ має три паліндроми непарної довжини з центрами в позиції $s[3] = b$, тобто $d_{odd}[3] = 3$:

$$a\ \overbrace{b\ a\ \underbrace{b}_{s_3}\ a\ b}^{d_{odd}[3]=3} c$$

А рядок $s = cbaabd$ має два паліндроми парної довжини з центрами в позиції $s[3] = a$, тобто $d_{even}[3] = 2$:

$$c\ \overbrace{b\ a\ \underbrace{a}_{s_3}\ b}^{d_{even}[3]=2} d$$

Дивовижний факт полягає в тому, що існує достатньо простий алгоритм, який обчислює ці «масиви паліндромності» $d_{odd}[]$ і $d_{even}[]$ за лінійний час. Цей алгоритм описано в цій статті.

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

• Задача про паліндроми (усі підпаліндроми, найдовший паліндром, кількість паліндромних підрядків)?
• Потрібен саме лінійний $O(n)$ розв'язок з малою сталою, а не $O(n \log n)$ через хеші? (якщо лінійність не критична → Хешування рядків)
• Достатньо інформації про паліндроми навколо центрів, без загальних запитів про довільні підрядки? (якщо потрібні підрядкові запити → Суфіксний автомат)

Розв'язок

Загалом ця задача має багато розв'язків: за допомогою хешування рядків її можна розв'язати за $O(n\cdot \log n)$, а за допомогою суфіксних дерев і швидкого LCA цю задачу можна розв'язати за $O(n)$.

Але описаний тут метод значно простіший і має меншу приховану сталу в складності за часом і пам'яттю. Цей алгоритм відкрив Glenn K. Manacher у 1975 році.

Ще один сучасний спосіб розв'язати цю задачу і працювати з паліндромами загалом — це так зване паліндромне дерево, або eertree.

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

Щоб уникнути неоднозначностей у подальшому викладі, позначимо, що таке «тривіальний алгоритм».

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

Такий алгоритм повільний — він може обчислити відповідь лише за $O(n^2)$.

Реалізація тривіального алгоритму:

C++

vector<int> manacher_odd_trivial(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    for(int i = 1; i <= n; i++) {
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

Python

def manacher_odd_trivial(s: str) -> list[int]:
    n = len(s)
    # символи-вартові, щоб не обробляти межі рядка окремо
    s = "$" + s + "^"
    p = [0] * (n + 2)
    for i in range(1, n + 1):
        # розширюємо паліндром навколо центру i, доки символи збігаються
        while s[i - p[i]] == s[i + p[i]]:
            p[i] += 1
    return p[1:n + 1]

TypeScript

function manacherOddTrivial(s: string): number[] {
    const n = s.length;
    // символи-вартові, щоб не обробляти межі рядка окремо
    s = "$" + s + "^";
    const p = new Array<number>(n + 2).fill(0);
    for (let i = 1; i <= n; i++) {
        // розширюємо паліндром навколо центру i, доки символи збігаються
        while (s[i - p[i]] === s[i + p[i]]) {
            p[i]++;
        }
    }
    return p.slice(1, n + 1);
}

Go

func manacherOddTrivial(s string) []int {
    n := len(s)
    // символи-вартові, щоб не обробляти межі рядка окремо
    s = "$" + s + "^"
    p := make([]int, n+2)
    for i := 1; i <= n; i++ {
        // розширюємо паліндром навколо центру i, доки символи збігаються
        for s[i-p[i]] == s[i+p[i]] {
            p[i]++
        }
    }
    return p[1 : n+1]
}

Кінцеві символи $ і ^ використано, щоб не обробляти кінці рядка окремо.

Алгоритм Манакера

Опишемо алгоритм для пошуку всіх підпаліндромів непарної довжини, тобто для обчислення $d_{odd}[]$.

Для швидкого обчислення ми підтримуватимемо виключні межі $(l, r)$ найправішого знайденого (під)паліндрома (тобто поточний найправіший (під)паліндром — це $s[l+1] s[l+2] \dots s[r-1]$). Спочатку ми встановлюємо $l = 0, r = 1$, що відповідає порожньому рядку.

Отже, ми хочемо обчислити $d_{odd}[i]$ для наступного $i$, причому всі попередні значення в $d_{odd}[]$ уже обчислені. Ми робимо таке:

• Якщо $i$ лежить поза поточним підпаліндромом, тобто $i \geq r$, ми просто запускаємо тривіальний алгоритм.

  Тобто ми послідовно збільшуємо $d_{odd}[i]$ і щоразу перевіряємо, чи є поточний найправіший підрядок $[i - d_{odd}[i]\dots i + d_{odd}[i]]$ паліндромом. Коли ми знаходимо перше неспівпадіння або досягаємо меж $s$, ми зупиняємось. У цьому випадку ми остаточно обчислили $d_{odd}[i]$. Після цього не слід забути оновити $(l, r)$. Значення $r$ потрібно оновити так, щоб воно відповідало останньому індексу поточного найправішого підпаліндрома.

• Тепер розглянемо випадок, коли $i \le r$. Ми спробуємо видобути певну інформацію з уже обчислених значень у $d_{odd}[]$. Отже, знайдемо «дзеркальну» позицію $i$ у підпаліндромі $(l, r)$, тобто отримаємо позицію $j = l + (r - i)$, і перевіримо значення $d_{odd}[j]$. Оскільки $j$ — це позиція, симетрична до $i$ відносно $(l+r)/2$, ми майже завжди можемо присвоїти $d_{odd}[i] = d_{odd}[j]$. Ілюстрація цього (паліндром навколо $j$ фактично «копіюється» в паліндром навколо $i$):

  $$\ldots\ \overbrace{ s_{l+1}\ \ldots\ \underbrace{ s_{j-d_{odd}[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_{odd}[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ s_{r-1}\ }^\text{palindrome}\ \ldots$$

  Але є хитрий випадок, який треба обробити коректно: коли «внутрішній» паліндром досягає меж «зовнішнього», тобто $j - d_{odd}[j] \le l$ (або, що те саме, $i + d_{odd}[j] \ge r$). Оскільки симетрія поза «зовнішнім» паліндромом не гарантована, просто присвоїти $d_{odd}[i] = d_{odd}[j]$ буде неправильно: у нас недостатньо даних, щоб стверджувати, що паліндром у позиції $i$ має таку саму довжину.

  Насправді нам поки що слід обмежити довжину нашого паліндрома, тобто присвоїти $d_{odd}[i] = r - i$, щоб коректно обробити такі ситуації. Після цього ми запустимо тривіальний алгоритм, який спробує збільшити $d_{odd}[i]$, доки це можливо.

  Ілюстрація цього випадку (паліндром із центром $j$ обмежено так, щоб він уміщувався в «зовнішній» паліндром):

  $$\ldots\ \overbrace{ \underbrace{ s_{l+1}\ \ldots\ s_j\ \ldots\ s_{j+(j-l)-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)+1}\ \ldots\ s_i\ \ldots\ s_{r-1} }_\text{palindrome}\ }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here}$$

  На ілюстрації показано, що паліндром із центром $j$ міг би бути більшим і виходити за межі «зовнішнього» паліндрома, але з центром у $i$ ми можемо використати лише ту частину, яка повністю вміщується в «зовнішній» паліндром. Проте відповідь для позиції $i$ ($d_{odd}[i]$) може бути значно більшою за цю частину, тому далі ми запустимо наш тривіальний алгоритм, який спробує розширити її за межі нашого «зовнішнього» паліндрома, тобто в область «спробувати рухатись сюди».

І знову, ми не повинні забути оновити значення $(l, r)$ після обчислення кожного $d_{odd}[i]$.

Складність алгоритму Манакера

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

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

Можна помітити, що кожна ітерація тривіального алгоритму збільшує $r$ на одиницю. Також $r$ не може зменшуватись протягом роботи алгоритму. Отже, тривіальний алгоритм зробить $O(n)$ ітерацій загалом.

Інші частини алгоритму Манакера, очевидно, працюють за лінійний час. Таким чином, ми отримуємо часову складність $O(n)$.

Реалізація алгоритму Манакера

Для обчислення $d_{odd}[]$ ми отримуємо такий код. На що слід звернути увагу:

• $i$ — це індекс центральної літери поточного паліндрома.
• Якщо $i$ перевищує $r$, $d_{odd}[i]$ ініціалізується нулем.
• Якщо $i$ не перевищує $r$, то $d_{odd}[i]$ або ініціалізується значенням $d_{odd}[j]$, де $j$ — дзеркальна позиція $i$ в $(l,r)$, або $d_{odd}[i]$ обмежується розміром «зовнішнього» паліндрома.
• Цикл while позначає тривіальний алгоритм. Ми запускаємо його незалежно від значення $k$.
• Якщо розмір паліндрома з центром у $i$ дорівнює $x$, то $d_{odd}[i]$ зберігає $\frac{x+1}{2}$.

C++

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for(int i = 1; i <= n; i++) {
        if(i <= r) {
            p[i] = min(r - i, p[l + (r - i)]);
        }
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

Python

def manacher_odd(s: str) -> list[int]:
    n = len(s)
    s = "$" + s + "^"
    p = [0] * (n + 2)
    # (l, r) — виключні межі найправішого знайденого паліндрома
    l, r = 0, 1
    for i in range(1, n + 1):
        if i <= r:
            # використовуємо дзеркальну позицію, не виходячи за межу r
            p[i] = min(r - i, p[l + (r - i)])
        # тривіальний алгоритм: розширюємо паліндром навколо центру i
        while s[i - p[i]] == s[i + p[i]]:
            p[i] += 1
        # оновлюємо найправіший паліндром
        if i + p[i] > r:
            l, r = i - p[i], i + p[i]
    return p[1:n + 1]

TypeScript

function manacherOdd(s: string): number[] {
    const n = s.length;
    s = "$" + s + "^";
    const p = new Array<number>(n + 2).fill(0);
    // (l, r) — виключні межі найправішого знайденого паліндрома
    let l = 0, r = 1;
    for (let i = 1; i <= n; i++) {
        if (i <= r) {
            // використовуємо дзеркальну позицію, не виходячи за межу r
            p[i] = Math.min(r - i, p[l + (r - i)]);
        }
        // тривіальний алгоритм: розширюємо паліндром навколо центру i
        while (s[i - p[i]] === s[i + p[i]]) {
            p[i]++;
        }
        // оновлюємо найправіший паліндром
        if (i + p[i] > r) {
            l = i - p[i];
            r = i + p[i];
        }
    }
    return p.slice(1, n + 1);
}

Go

func manacherOdd(s string) []int {
    n := len(s)
    s = "$" + s + "^"
    p := make([]int, n+2)
    // (l, r) — виключні межі найправішого знайденого паліндрома
    l, r := 0, 1
    for i := 1; i <= n; i++ {
        if i <= r {
            // використовуємо дзеркальну позицію, не виходячи за межу r
            p[i] = min(r-i, p[l+(r-i)])
        }
        // тривіальний алгоритм: розширюємо паліндром навколо центру i
        for s[i-p[i]] == s[i+p[i]] {
            p[i]++
        }
        // оновлюємо найправіший паліндром
        if i+p[i] > r {
            l, r = i-p[i], i+p[i]
        }
    }
    return p[1 : n+1]
}

Робота з парностями

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

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

$$abcbcba \to \#a\#b\#c\#b\#c\#b\#a\#,$$ $$d = [1,2,1,2,1,4,1,8,1,4,1,2,1,2,1].$$

Як бачите, $d[2i]=2 d_{even}[i]+1$ і $d[2i+1]=2 d_{odd}[i]$, де $d$ позначає масив Манакера для паліндромів непарної довжини в рядку, з'єднаному символами #, а $d_{odd}$ і $d_{even}$ відповідають масивам, означеним вище для початкового рядка.

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

Зауважимо, що $d[2i]$ і $d[2i+1]$ — це, по суті, збільшені на $1$ довжини найбільших паліндромів непарної та парної довжини відповідно з центром у $i$.

Це зведення реалізовано так:

C++

vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

Python

def manacher(s: str) -> list[int]:
    # вставляємо роздільник '#' між символами та з обох боків
    t = ""
    for c in s:
        t += "#" + c
    res = manacher_odd(t + "#")
    return res[1:len(res) - 1]

TypeScript

function manacher(s: string): number[] {
    // вставляємо роздільник '#' між символами та з обох боків
    let t = "";
    for (const c of s) {
        t += "#" + c;
    }
    const res = manacherOdd(t + "#");
    return res.slice(1, res.length - 1);
}

Go

func manacher(s string) []int {
    // вставляємо роздільник '#' між символами та з обох боків
    t := ""
    for _, c := range s {
        t += "#" + string(c)
    }
    res := manacherOdd(t + "#")
    return res[1 : len(res)-1]
}

Для простоти розбиття масиву на $d_{odd}$ і $d_{even}$, а також їх явне обчислення тут опущено.

Задачі

• Library Checker - Enumerate Palindromes
• Longest Palindrome
• UVA 11475 - Extend to Palindrome
• GYM - (Q) QueryreuQ
• CF - Prefix-Suffix Palindrome
• SPOJ - Number of Palindromes
• Kattis - Palindromes

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