if(i<r) p[z][i]=min(r-i+!z,p[z][l+r-i+!z]);

Ну просто охренеть как читаемо.

Можно писать алгоритм только для строк нечетной длины, но при этом будет использовано немного больше памяти. Если у нас строка четной длины, например abba, то её можно преобразовать в строку a#b#b#a.

Расскажите кто-нибудь, где ошибка в манагере с e-maxx. Он нормально сдавался вроде в какой-то из здешних задач.

Ну, думаю, читаемость тут уже на вкус и цвет. Мне нравится вот эта реализация.

Why are you down voting him? He is describing an algorithm.

.

I think this may be helpful : http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

I solved that problem in O(N*logN) using Hash. I think Hashing can replace Manacher entirely, can apply to more types of problem and is easier to implement :)

hey you sucker .... you published this before 2 days and APIO contest was running ... this algorithm is very useful for the first task

If i've read this during APIO I would've scored 100 points on the first task

and guess what it was published DURING THE CONTEST

Here is the link to my implementation, it's a bit different to your code. Also it includes a function (quiet trivial) that is useful for checking if a given substring s[b...e] is palindrome.

.

А не проще ли делать все не с начальной строкой, а строкой, между символов которой вставлен символ, допустим, #(тут даже не имеет значение, входит ли этот символ в начальный алфавит). Например, abacaba заменить на a#b#a#c#a#b#a. Тогда все палиндромы четной длины будут просто палиндромами, в центре которых #, в свою очередь нечетной — те, у которых в центре буква. То есть, центральный символ будет у всех. Таким образом, все палиндромы, найденные в новой строке, будут нечетной длины. Тогда не надо будет писать два разных алгоритма, проигрыша во времени тогда очевидно не будет(потому что не надо проверять строку на два различных типа палиндромов, четных и нечетных), по памяти в два раза. Но читаемость значительно повысится.

UPD увидел выше.

Can you please explain how you solved the Timus problem 1937 using Manacher's algorithm?

How common are Manachers' algo problems on Codeforces? Could someone give me links to some questions here on Codeforces.

Huh, readability is incredible in this article :)

Here is actual version:

vector<int> pal_array(string s)
{
    int n = s.size();
    s = "@" + s + "$";
    vector<int> len(n + 1);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++)
    {
        len[i] = min(r - i, len[l + (r - i)]);
        while(s[i - len[i]] == s[i + len[i]])
            len[i]++;
        if(i + len[i] > r)
        {
            l = i - len[i];
            r = i + len[i];
        }
    }
    len.erase(begin(len));
    return len;
}

We can also solve this problem using Dynamic Programming using O(N^2) time and memory. We will store array dp[i][j] to memoize the function: f(i,j) = 1 if substring [i..j] is palindrome and 0 otherwise.

The base cases are all f(i,i) because a length 1 substring is always a palindrome, and also f(i,i+1) is a base case, because if s[i] = s[i+1] then f(i,i+1) = 1, otherwise f(i,i+1) = 0.

When i < j-1, f(i,j) = 1 iff f(i+1,j-1) = 1 and s[i] = s[j], otherwise f(i,j) = 0. So we can run f(i,j) for every pair (i,j) and in the end we will have a boolean matrix that will contain the indices (i,j) of every palindromic substring.

This algorithm should be optimal because we can have O(N^2) palindromic substrings (when every character is equal), so any algorithm that retrieves all of them should be at least O(N^2).

Here is my version:

vector<int> manacherL(const string& s) {
    const int n = (int)s.length();
    if (n == 0)
        return vector<int>();
    vector<int> res(2*n - 1);
    int p = 0, pR = -1;
    for (int pos = 0; pos < 2*n - 1; ++pos) {
        int R = pos <= 2*pR ? min(p - res[2*p - pos], pR) : pos/2;
        int L = pos - R;
        while (L > 0 && R < n-1 && s[L-1] == s[R+1]) {
            --L;
            ++R;
        }
        res[pos] = L;
        if (R > pR) {
            pR = R;
            p = pos;
        }
    }
    return res;
}

It returns the array L[i] — index of the beginning of the longest palindrome centered at position i. (For both even and odd positions simultaneously.) If you need the end index, it is calculated by symmetry: R[i] = i - L[i]. And of course, the length of the palindrome is len[i] = R[i]-L[i]+1 = i - 2*L[i] + 1.

I found much shorter implementation https://github.com/stjepang/snippets/blob/master/manacher.cpp

I like this implementation:

ll manak(str t){
    int a = t.size();
    vec<int> m(a);
    ll o = 0;
    for(int q=0, l=0, r=0; q<a; o+=m[q], l = q+m[q]-1>r ? q-m[q]+1 : l, r = max(r, q+m[q]-1), q++) for(m[q] = max(0, min(r-q, m[r-q+l])); q+m[q]<a && q-m[q]>=0 && t[q-m[q]]==t[q+m[q]];) m[q]++;
    for(int q=1, l=0, r=0; q<a; o+=m[q], l = q+m[q]>r ? q-m[q]-1 : l, r = max(r, q+m[q]), q++) for(m[q] = max(0, min(r-q, m[r-q+l+1])); q+m[q]<a && q-m[q]>=1 && t[q-m[q]-1]==t[q+m[q]];) m[q]++;
    return o;
}

for(i = 0; i < n; i++){ if(i > r) k = 1; else k = min(d1[l + r — i], r — i);

while(0 <= i-k && i+k < n && s[i — k] == s[i + k]) k++; d1[i] = k; if(i + k — 1 > r) r = i + k — 1, l = i — k + 1; }

for(i = 0; i < n; i++){ if(i > r) k = 0; else k = min(d2[l + r — i + 1], r — i + 1);

while(i + k < n && i — k — 1 >= 0 && s[i+k] == s[i — k — 1]) k++; d2[i] = k;

if(i + k — 1 > r) l = i — k, r = i + k — 1; }

adamant Это очень полезный материал.

Только, можно уже исправить реализация, https://cp-algorithms.com/string/manacher.html ?

Многие не читают комментарий и сразу смотрят реализация в основном материале (включая я :).

one bug in your given code in odd length manacher's array it is k = (i>r ? 0 : min (d1[l+r-i], r-i)); not k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;

Is above piece of code works for both odd and even length palindromes or we have to do something more for even length palindromes ??