题解 P3649 【[APIO2014]回文串】

· · 题解

看楼上各位Dalao都是用的回文树等数据结构做的，真是太神了。

这道题网上普遍有3种做法：

1.回文树裸题 2.SAM+manacher 3.SA+manacher

后两者的大体思路都是结合manacher性质找出所有回文串，然后上数据结构统计次数的。

我来介绍一种只用后缀自动机的做法。

这种做法是从2015年国家集训队论文中看来，张天扬也没有进行详细地解答，也找不到《APOI2014 回文串 解题报告》，只能靠自己对着标程一点一点理解。

这种做法的大体是这样的：对于原串建立SAM，对于每个状态我们保存其endpos的maxpos。然后将反串放上去跑（我们通过从右往左扫来实现，所以下述的所有位置都是指的原串的位置）。如果当前反串中的匹配串[l,r]覆盖了当前节点的maxpos，那么[l,maxpos]是一个回文串。

　　

这样的话，我们就可以通过状态出现的次数，轻松地算出贡献了。

接着我们要不断跳link边（也就是跳后缀树上的边），再次统计答案。并标记经过的点，之后不再经过已标记的点。

那么我们会有几个疑惑。

1.为什么要记录maxpos？为什么这样是对的？

我们假设绿色位置也属于该状态的endpos，同时红绿两点间形成一个回文串，而反串位置和maxpos间无法形成回文。

设反串位置为i，绿色位置为pos，匹配长度为len

已知pos-len<i，由于该状态的maxlen一定大于len,[i,pos]是个回文串

所以[maxpos-len,maxpos]这个区间也是个回文串。这个回文串的答案会在maxpos-len的时候贡献。

所以记录maxpos一定是对的。

2.为什么要跳link边？

已知，link边指向的节点，代表着该后缀的最长不同endpos的后缀，同时link边指向的节点的maxpos必定大于等于当前节点的maxpos。也就是说在link边指向的节点可能存在更优解，我们需要进行更新的答案。但注意当你跳link的时候，匹配的长度就不再是len了，而是该状态的maxlen。

打标记是为了优化常数。

这样这个题就解决了。

至于打标记为什么不会漏解的问题，我现在也没想明白。等明白了再更新。

看看代码可能大家就懂了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define o 1000011
#define ll long long
using namespace std;

struct node{
    int link,len,nxt[26],maxpos;
    void clear(){
        link=-1;len=0;maxpos=0;
        for(int i=0;i<26;i++) nxt[i]=0;
    }
}st[o];
char s[o];
int size,last,len,b[o],cc[o];
ll dp[o],ans;
bool vis[o];
void init(){
    st[0].clear();
    size=last=0;
}
void insert(char c,int pos){
    int cur=++size;
    st[cur].clear();
    st[cur].len=st[last].len+1;
    st[cur].maxpos=pos;
    dp[cur]=1;
    int p,x=c-'a';
    for(p=last;p!=-1&&!st[p].nxt[x];p=st[p].link) st[p].nxt[x]=cur;
    if(p==-1)
        st[cur].link=0;
    else{
        int q=st[p].nxt[x];
        if(st[p].len+1==st[q].len)
            st[cur].link=q;
        else{
            int clone=++size;
            st[clone].clear();
            st[clone].len=st[p].len+1;
            st[clone].link=st[q].link;
            st[clone].maxpos=st[q].maxpos;
            for(int i=0;i<26;i++) st[clone].nxt[i]=st[q].nxt[i];
            for(;p!=-1&&st[p].nxt[x]==q;p=st[p].link) st[p].nxt[x]=clone;
            st[q].link=st[cur].link=clone;
        }
    }
    last=cur;
}
int main(){
    init();
    scanf("%s",s);
    len=strlen(s);
    for(int i=0;i<len;i++) insert(s[i],i);
    for(int i=0;i<=size;i++) cc[st[i].len]++;
    for(int i=1;i<=len;i++) cc[i]+=cc[i-1];
    for(int i=0;i<=size;i++) b[--cc[st[i].len]]=i; 
    for(int i=size;i;i--){
        st[st[b[i]].link].maxpos=max(st[st[b[i]].link].maxpos,st[b[i]].maxpos);
        dp[st[b[i]].link]+=dp[b[i]];
    }
    int now=0,l=0;
    for(int i=len-1;i>=0;i--){
        while(now&&!st[now].nxt[s[i]-'a']){
            now=st[now].link;
            l=st[now].len;
        }
        if(st[now].nxt[s[i]-'a']){
            now=st[now].nxt[s[i]-'a'];
            l++;
        }
        if(st[now].maxpos<i+l){
            if(i<=st[now].maxpos)
                ans=max(ans,(ll)(st[now].maxpos-i+1)*dp[now]);
            for(int p=st[now].link;p!=-1&&!vis[p];p=st[p].link){
                vis[p]=true;
                if(i<=st[p].maxpos&&st[p].maxpos<=i+st[p].len-1)
                    ans=max(ans,(ll)(st[p].maxpos-i+1)*dp[p]);
            }    
        }        
    }
    printf("%lld\n",ans);
    return 0;
}