题解 P3900 【[湖南集训]图森】

· · 题解

我们先考虑一个暴力的解法：暴力枚举回文串的对称轴（可能是某个字符串的单个字符，也有可能是两个字符中间的空格，甚至有可能是两个不同串首尾拼接在一起的接口），然后向两边扩张，直到不能再扩为止。

显然，除了一开始的初始状态以外，这个对称轴是没有意义的——我们只需要记录当前回文串最左端的位置和最右端的位置即可。

我们将所有串全都拼在一起，成为一个大串s。设f[l,r]表示当前回文串左端点在l，右端点在r，它继续往前延伸能伸到的的最长长度。注意到这里不一定有l<r，因为这个l和r可以被看做两个指针，它指向了原来两个串中的某个位置，只不过为了消减维数给强行拼在一起而已。

设st_i为原本的某个串i在新串中的起始位置，ed_i为i在新串中的截止位置。

则有

f[l,r]=\begin{cases}0(s_l\neq s_r)\\f[l-1,r+1]+2(l\neq st_i,r\neq ed_j)\\f[ed_k,r+1]+2(l=st_i,r\neq ed_j)\\f[l-1,st_k]+2(l\neq st_i,r=ed_j)\\\infty(l=st_i,r=ed_j)\end{cases}

其中，i,j,k均指任何一个原串。

显然，上面的转移式中，(1),(2)是比较容易理解的；(3),(4)的意义是一个串已经被全部拼完了，又接上了另一个串；(5)的意义是[l,r]本身就是一个回文串，则只要它自己不断拼接下去，回文串的长度就是无限的，因此答案就是\infty。

显然，这个DP的复杂度是O\Big(n(\sum|S|)^2\Big)的，不可能跑过去。则我们考虑优化。

我们发现，一个f[l,r]，只要它们没有任何一个碰到边界，则l会一直-1，r会一直+1；所以我们只需要求出（以l为结尾的所有子串）同（以r为开头的所有子串）中最长的相同串，即是它们最终会延伸到的长度。

因此我们求出这个长度之后，l和r就可以直接延伸到对应的地方。设一个延伸到L，一个延伸到R。则我们照着上面的转移式转移即可。

则我们现在就可以把维数消减掉一维了。我们设f[x][0/1]表示x是r/l，且另外一个指针指到了某个串的端点处时，它最远能延伸多远。

则我们在转移的时候，只需要枚举新拼接上的那个串是什么，然后求出它最终延伸的长度即可转移。

这一段是使用记忆化搜索实现的DP：

int dfs(int x,bool tp){//tp=0:x is the starting point of a suffix;tp=1:the ending point of a prefix.(can refer to PAL function)
    if(vis[x][tp]){puts("Infinity");exit(0);}//a circle occurs, and the answer equals inf.
    if(f[x][tp]!=-1)return f[x][tp];//memorized searching
    vis[x][tp]=true;
    int &now=f[x][tp];now=0;
    if(!tp){
        for(int i=1;i<=all;i++){//numerate the string we're going to concatenate.
            int len=PAL(x,ed[i]);//get the maximum palindrome length
            int L=ed[i]-len+1,R=x+len-1;
            if(L!=st[i]&&R!=ed[id[x]])now=max(now,len<<1);//no string can reach to the end,so k is the maximal parlindrome length
            else if(L==st[i])now=max(now,(len<<1)+dfs(R+1,false));//the whole string i is matched
            else if(R==ed[id[x]])now=max(now,(len<<1)+dfs(L-1,true));//the whole string id[x] is matched
            else{puts("Infinity");exit(0);}//both strings are matched, which means there is a palindrome string, and the answer is inf.
        }
    }else{//similar to the above function
        for(int i=1;i<=all;i++){
            int len=PAL(st[i],x);
            int L=x-len+1,R=st[i]+len-1;
            if(L!=st[id[x]]&&R!=ed[i])now=max(now,len<<1);
            else if(L==st[id[x]])now=max(now,(len<<1)+dfs(R+1,false));
            else if(R==ed[i])now=max(now,(len<<1)+dfs(L-1,true));
            else{puts("Infinity");exit(0);}
        }
    }
    vis[x][tp]=false;
    return now;
}

首先，如果你到了一个位置，发现它成环了，则我们只需要在这个环上不停地绕，回文串的长度就会不断增加，因此答案就是\infty；否则，正常记忆化搜索即可。

注意到那个PAL(x,y)函数，这是一个用来求当r=x,l=y时，最长可以延伸到多远的函数。它可以使用后缀数组+ST表做到O(n\log n)预处理，O(1)回答。而id_x，则表示新串中位置为x的那个字符原本是在哪个原串中的。

然后在主函数里我们只需要枚举对称轴即可。显然，这个对称轴数量是O(\sum|S|)的，因此可以枚举。

则总复杂度为O\Big(\sum|S|\big(n+\log(sum|S|)\big)\Big)。

代码（附详细英文版注释）：

#include<bits/stdc++.h>
using namespace std;
const int N=200100;
int all,st[110],ed[110],id[N],res;
namespace Suffix_Array{
    int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m;
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<=n)^(b+k<=n))return false;
        if((a+k<=n)&&(b+k<=n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)sa[buc[x[i]]--]=i;
        for(int k=1;k<=n;k<<=1){
            int num=0;
            for(int i=n-k+1;i<=n;i++)y[++num]=i;
            for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=1;i<=n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i];
            swap(x,y);
            x[sa[1]]=num=1;
            for(int i=2;i<=n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(n==num)break;
            m=num;
        }
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        for(int i=1,k=0;i<=n;i++){
            if(rk[i]==1)continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
    }
}
using namespace Suffix_Array;
namespace Sparse_Table{
    int LG[N],mn[N][20];
    void ST(){
        for(int i=2;i<=n;i++)LG[i]=LG[i>>1]+1;
        for(int i=1;i<=n;i++)mn[i][0]=ht[i];
        for(int j=1;j<=LG[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    }
    int LCP(int x,int y){//ask the LCP of two suffixes
        if(x==y)return ed[id[x]]-st[id[x]]+1;//the LCP of two same strings is the string itself
        x=rk[x],y=rk[y];
        if(x>y)swap(x,y);
        x++;
        int k=LG[y-x+1];
        return min(mn[x][k],mn[y-(1<<k)+1][k]);
    }
    int PAL(int x,int y){//return the maximal length of a common string that is both a suffix starting from index x and a prefix ending at index y
        return min(LCP(x,n-y+1),min(ed[id[x]]-x+1,y-st[id[y]]+1));//can't go over the length of original strings
    } 
}
using namespace Sparse_Table;
bool vis[N][2];//use the vis array to avoid circles
int f[N][2];
int dfs(int x,bool tp){//tp=0:x is the starting point of a suffix;tp=1:the ending point of a prefix.(can refer to PAL function)
    if(vis[x][tp]){puts("Infinity");exit(0);}//a circle occurs, and the answer equals inf.
    if(f[x][tp]!=-1)return f[x][tp];//memorized searching
    vis[x][tp]=true;
    int &now=f[x][tp];now=0;
    if(!tp){
        for(int i=1;i<=all;i++){//numerate the string we're going to concatenate.
            int len=PAL(x,ed[i]);//get the maximum palindrome length
            int L=ed[i]-len+1,R=x+len-1;
            if(L!=st[i]&&R!=ed[id[x]])now=max(now,len<<1);//no string can reach to the end,so k is the maximal parlindrome length
            else if(L==st[i])now=max(now,(len<<1)+dfs(R+1,false));//the whole string i is matched
            else if(R==ed[id[x]])now=max(now,(len<<1)+dfs(L-1,true));//the whole string id[x] is matched
            else{puts("Infinity");exit(0);}//both strings are matched, which means there is a palindrome string, and the answer is inf.
        }
    }else{//similar to the above function
        for(int i=1;i<=all;i++){
            int len=PAL(st[i],x);
            int L=x-len+1,R=st[i]+len-1;
            if(L!=st[id[x]]&&R!=ed[i])now=max(now,len<<1);
            else if(L==st[id[x]])now=max(now,(len<<1)+dfs(R+1,false));
            else if(R==ed[i])now=max(now,(len<<1)+dfs(L-1,true));
            else{puts("Infinity");exit(0);}
        }
    }
    vis[x][tp]=false;
    return now;
}
int main(){
    scanf("%d",&all);
    for(int i=1;i<=all;i++){
        scanf("%s",s+n+1);
        m=strlen(s+n+1);
        st[i]=n+1;
        for(int j=n+1;j<=n+m;j++)s[j]=s[j]-'a'+1,id[j]=i;
        n+=m;
        ed[i]=n;//st is the starting index after concatenating all the strings,while ed is the ending index
    }
    for(int i=1;i<=n;i++)s[2*n-i+1]=s[i];//reverse the string and concatenating it after the original string
    n<<=1,m=26,SA(),ST();
//  for(int i=1;i<=all;i++)printf("(%d,%d)",st[i],ed[i]);puts("");
//  for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
//  for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
    memset(f,-1,sizeof(f));
    for(int i=1;i<=all;i++){
        res=max(res,max(dfs(st[i],false),dfs(ed[i],true)));//palindromes that symmetrix axis is between two different strings
        for(int j=st[i];j<=ed[i];j++){//palindromes that symmetric axis is a character
            int len=PAL(j,j);//the maximal palindrome length
            int L=j-len+1,R=j+len-1;
            if(L!=st[i]&&R!=ed[i])res=max(res,(len<<1)-1);//minus one, as the symmetrix axis is calculated twice
            else if(L==st[i])res=max(res,(len<<1)-1+dfs(R+1,false));
            else if(R==ed[i])res=max(res,(len<<1)-1+dfs(L-1,true));
            else{puts("Infinity");exit(0);}
        }
        for(int j=st[i];j<ed[i];j++){//palindromes that symmetric axis is the blank between two characters
            int len=PAL(j+1,j);
            int L=j-len+1,R=(j+1)+len-1;
            if(L!=st[i]&&R!=ed[i])res=max(res,len<<1);
            else if(L==st[i])res=max(res,(len<<1)+dfs(R+1,false));
            else if(R==ed[i])res=max(res,(len<<1)+dfs(L-1,true));
            else{puts("Infinity");exit(0);}         
        }
    }
    printf("%d\n",res);
    return 0;
}