[POI 19 Stage 3] Prefixuffix

作法：

假設長度為$L$的前綴後綴為答案，那麼可以知道一定存在一個$k$，使得$S[1,...,k]$和$S[n-k+1,...,n]$長的一模一樣，並且$S[k+1,...,L]$和$S[n-L+1...n-k]$一模一樣（跟題目條件等價）。前面的條件很好檢查，不管是用 hash 還是 Z value 都可以。至於後面那個條件，這時我們需要知道：給定一個$i$，找出最長的長度$L$使得$S[i,...,n+1-i]$這個字串的長$L$的前綴和長$L$的後綴長的一模一樣。也就是我們關心的是位子關於整個字串中點對稱的長的一模一樣的字串。具體來說就是一些$(x,y)$滿足$S[x,...,y]$和$S[n+1-y,...,n+1-x]$長的一模一樣。我們考慮枚舉$(x,y)$數對的中點，那麼可以先二分搜出以某個點為中點的話滿足條件的$(x,y)$最多可以擴展到哪裡（因為有個性質是$(x,y)$滿足的話$(x+1,y-1)$也滿足）。假設我們二分搜出了$(L,R)$這段區間是滿足的，也就是$S[L,...,R]=S[n+1-R,...,n+1-L]$，並且$(L-1,R+1)$不滿足，令$len[i]$代表最大的「滿足$S[i+1,...,n-i]$的長$len[i]$的前綴和長$len[i]$的」的數，那麼這時就要用$R-L+1$去更新$len[L-1]$，$R-L-1$去更新$len[L]$，以此類推直到更新的值$<0$為止。這樣就可以直接往左往右掃得到每個$len$值了，只要當我們收到「把$a$和$x$取 max ，把$a+1$和$x-2$取 max ，...」時在$a$上紀錄$x+2a$的值，並在掃描過程中維護好這個數的值的最大值就可以了。

code :

#include<stdio.h>
#include<algorithm>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=1000000+10 ;
const int X=13 ;
 
LL ha[maxn],pw[maxn] ;
inline LL gethash(int l,int r)
{
    LL ret=ha[r]-ha[l-1]*pw[r-l+1]%MOD ;
    return ret<0 ? ret+MOD : ret ;
}
 
inline bool check(int L1,int R1,int L2,int R2)
{
    return gethash(L1,R1)==gethash(L2,R2) ;
}
 
char s[maxn] ;
int val[maxn] ;
 
main()
{
    int n ; scanf("%d%s",&n,s+1) ;
    pw[0]=1 ;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*X%MOD , ha[i]=(ha[i-1]*X+s[i]-'a')%MOD ;
 
    for(int i=0;i<=n;i++) val[i]=-maxn ;
    for(int i=2;i<=(n/2)*2;i++)
    {
        int x=i/2 , y=(i+1)/2 ;
        if(s[n+1-y]!=s[x] || s[n+1-x]!=s[y]) continue ;
        int l=1 , r=min(x,n/2-y+1)+1 ;
        while(r-l>1)
        {
            int mid=(r+l)/2 ;
            if(check(x-mid+1,y+mid-1,n+1-(y+mid-1),n+1-(x-mid+1))) l=mid ;
            else r=mid ;
        }
        int L=(i%2 ? 2*l : 2*l-1) ;
        val[x-l]=max(val[x-l],L+2*(x-l)) ;
    }
 
    int ans=0 ;
    for(int i=0,ma=-maxn;2*i<=n;i++)
    {
        ma=max(ma,val[i]) ;
        if(!i || check(1,i,n+1-i,n)) ans=max(ans,ma-2*i+i) , ans=max(ans,i) ;
    }
    printf("%d\n",ans) ;
}