string/manacher.hpp

View this file on GitHub
Last update: 2024-06-15 00:08:38+07:00
Include: #include "string/manacher.hpp"

Verified with

verify/yosupo/string/enumerate_palindromes.test.cpp

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-06-14
 * Description: Manacher's Algorithm. pal[i] := the length of the longest palindrome centered at i/2.
 */

template<class STR>
vector<int> manacher(const STR &s){
    int n=(int)s.size();
    if(n==0)return {};
    vector<int> pal(2*n-1);
    for(int p=0,l=-1,r=-1;p<2*n-1;p++){
        int i=(p+1)>>1,j=p>>1;
        int k=(i>=r?0:min(r-i,pal[2*(l+r)-p]));
        while(j+k+1<n&&i-k-1>=0&&s[j+k+1]==s[i-k-1])k++;
        pal[p]=k;
        if(j+k>r)l=i-k,r=j+k;
    }
    for(int i=0;i<2*n-1;i++)pal[i]=pal[i]<<1|(i&1^1);
    return pal;
}

#line 2 "string/manacher.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-14
 * Description: Manacher's Algorithm. pal[i] := the length of the longest palindrome centered at i/2.
 */

template<class STR>
vector<int> manacher(const STR &s){
    int n=(int)s.size();
    if(n==0)return {};
    vector<int> pal(2*n-1);
    for(int p=0,l=-1,r=-1;p<2*n-1;p++){
        int i=(p+1)>>1,j=p>>1;
        int k=(i>=r?0:min(r-i,pal[2*(l+r)-p]));
        while(j+k+1<n&&i-k-1>=0&&s[j+k+1]==s[i-k-1])k++;
        pal[p]=k;
        if(j+k>r)l=i-k,r=j+k;
    }
    for(int i=0;i<2*n-1;i++)pal[i]=pal[i]<<1|(i&1^1);
    return pal;
}