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

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

t

=

t_{r e v}

t = t_{rev}

Если $i$ находится за пределами текущего подпалиндрома, то есть $i \geq r$ , мы можем использовать простой подход, описанный выше.
Если $i \le r$ , то найдем "зеркальную" позицию $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$ имеет одинаковую длину.

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

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

Введение

Алгоритм

Простой подход

Алгоритм Манахера для строки нечетной длины

Алгоритм Манакера для общего случая