Manacher算法（Hotaru's problem，HDU 5371）

學習了Manacher算法

Manacher算法的介紹：

https://segmentfault.com/a/1190000003914228

Manacher算法的例題：

https://vjudge.net/problem/HDU-3068

例題代碼

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 110010;

char s[maxn];
char ss[maxn<<1];
int p[maxn<<1];
int len;

int manacher()
{
    int id=0;
    int mr=0;
    int ret=1;
    for(int i=0;i<=len;i++)
    {
        p[i]=mr>i?min(p[id*2-i],mr-i):1;
        while(0<=i-p[i]&&i+p[i]<=len&&ss[i-p[i]]==ss[i+p[i]]) p[i]++;
        if(i+p[i]>mr)
        {
            mr=i+p[i];
            id=i;
        }
        ret=max(ret,p[i]-1);
    }
    return ret;
}

void solve()
{
    len=strlen(s);
    for(int i=0;i<len;i++)
    {
        ss[(i<<1)+1]=s[i];
        ss[i<<1]='#';
    }
    len=len<<1;
    ss[len]='#';
    printf("%d\n",manacher());
}

int main()
{
    while(scanf("%s",s)!=EOF) solve();
    return 0;
}
           

本題代碼

#include<stdio.h>
#include<algorithm>
#include<set>
#include<math.h>
using namespace std;
const int maxn = 100010;

int n;
int a[maxn];
int aa[maxn<<1];
int p[maxn<<1];
int len;
int pp[maxn];
int r[maxn];

void read()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",a+i);
        aa[(i<<1)+1]=a[i];
        aa[i<<1]=-1;
    }
    len=n<<1;
    aa[len]=-1;
}

void manacher()
{
    int id=0;
    int mr=0;
    for(int i=0;i<=len;i++)
    {
        p[i]=i<mr?min(p[2*id-i],mr-i):1;
        while(0<=i-p[i]&&i+p[i]<=len&&aa[i-p[i]]==aa[i+p[i]]) p[i]++;
        if(i+p[i]>mr)
        {
            mr=i+p[i];
            id=i;
        }
    }
}

int cmp(int i,int j)
{
    return pp[i]>pp[j];
}

void solve()
{
    read();
    manacher();
    for(int i=0;i<n;i++)
    {
        pp[i+1]=p[i<<1];
        r[i+1]=i+1;
    }
    sort(r+1,r+1+n,cmp);
    int ans=0;
    set<int>s;
    for(int i=1;i<=n;i++)
    {
        int di = (pp[r[i]]-1)/2;
        int le = max(1,r[i]-di);
        int ri = min(n,r[i]+di);
        if(!s.empty())
        {
            set<int>::iterator it = s.lower_bound(le);
            if(it!=s.end()&&abs(r[i]-*it)<=di) ans=max(ans,abs(r[i]-*it));
            it = s.upper_bound(ri);
            if(it!=s.begin())
            {
                --it;
                if(abs(r[i]-*it)<=di) ans=max(ans,abs(r[i]-*it));
            }
        }
        s.insert(r[i]);
    }
    printf("%d\n",ans*3);
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        printf("Case #%d: ",t);
        solve();
    }
    return 0;
}