SGU 411 Petya the Hero

[cpp] 
求兩個字符串最長公共回文字串，並隨便輸出一個 
 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<algorithm> 
 
using namespace std; 
 
#define MAXN 10100 
 
int rad[MAXN]; 
char s[MAXN]; 
 
char r1[MAXN/2],r[MAXN]; 
int sa[MAXN]; 
int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; 
int height[MAXN],rank[MAXN]; 
 
int ans,start; 
inline bool cmp(int *r,int a,int b,int len){ 
    return r[a]==r[b]&&r[a+len]==r[b+len]; 
} 
void SA(int n,int m){ 
    int i,j,p,*x=wa,*y=wb,*t; 
    for(i=0;i<m;i++) 
        ws[i]=0; 
    for(i=0;i<n;i++) 
        ws[x[i]=r[i]]++; 
    for(i=1;i<m;i++) 
        ws[i]+=ws[i-1]; 
    for(i=n-1;i>=0;i--) 
        sa[--ws[x[i]]]=i; 
    for(j=p=1;p<n;j<<=1,m=p){ 
        for(p=0,i=n-j;i<n;i++) 
            y[p++]=i; 
        for(i=0;i<n;i++){ 
            if(sa[i]>=j) 
                y[p++]=sa[i]-j; 
        } 
        for(i=0;i<m;i++) 
            ws[i]=0; 
        for(i=0;i<n;i++) 
            ws[wv[i]=x[y[i]]]++; 
        for(i=1;i<m;i++) 
            ws[i]+=ws[i-1]; 
        for(i=n-1;i>=0;i--) 
            sa[--ws[wv[i]]]=y[i]; 
        for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++) 
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 
    } 
} 
void Height(int n){ 
    int i,j,k=0; 
    for(i=1;i<=n;i++) 
        rank[sa[i]]=i; 
    for(i=0;i<n;height[rank[i++]]=k) 
        for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); 
} 
 
void Manacher(char str[],int n){ 
    int i,mx=0,id; 
    for(i=1;i<n;i++){ 
        if(mx>i) rad[i]=min(rad[2*id-i],mx-i); 
        else rad[i]=0; 
        for(;str[i+rad[i]]==str[i-rad[i]];rad[i]++) 
            ; 
        rad[i]--; 
        if(mx<rad[i]+i){ 
            mx=rad[i]+i; 
            id=i; 
        } 
    } 
} 
 
int make_string(int mid){ 
    strcpy(r,r1); 
    r[mid]='#'; 
    scanf("%s",r+mid+1); 
    return strlen(r); 
} 
 
void cal_str(int from,int len){ 
    int i; 
    s[0]='$'; 
    for(i=0;i<len;i++){ 
        s[2*i+1]='#'; 
        s[2*i+2]=r1[i+from]; 
    } 
    s[2*len+1]='#'; 
    s[2*len+2]='@'; 
    Manacher(s,2*len+2); 
    int t=0; 
    for(i=1;i<=2*len+1;i++){ 
        if(rad[i]>ans){ 
            ans=rad[i]; 
            start=from+t-rad[i]/2; 
        } 
        if(s[i]!='#') 
            t++; 
    } 
} 
 
int main(){ 
    int n,mid; 
    memset(height,0,sizeof(height)); 
    scanf("%s",r1); 
    mid=strlen(r1); 
    n=make_string(mid); 
    SA(n+1,130); 
    Height(n); 
    ans=0; 
    for(int i=2;i<=n;i++){ 
        if(sa[i-1]<mid && sa[i]>mid) 
            cal_str(sa[i-1],height[i]); 
        else if(sa[i]<mid && sa[i-1]>mid) 
            cal_str(sa[i],height[i]); 
    } 
    for(int i=0;i<ans;i++) 
        printf("%c",r1[start+i]); 
    printf("\n"); 
} 

法二：直接對兩個串搞manacher，然後枚舉2個串上的位置，n^2的dp來搞

[cpp] 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<algorithm> 
#define MAXN 4010 
using namespace std; 
 
int rad1[MAXN],rad2[MAXN]; 
char s1[MAXN],s2[MAXN],str1[MAXN],str2[MAXN]; 
int ans,start; 
int dp[MAXN][MAXN]; 
void Manacher(int rad[],char str[],int n){ 
    int i,mx=0,id; 
    for(i=1;i<n;i++){ 
        if(mx>i) rad[i]=min(rad[2*id-i],mx-i); 
        else rad[i]=0; 
        for(;str[i+rad[i]]==str[i-rad[i]];rad[i]++) 
            ; 
        rad[i]--; 
        if(mx<rad[i]+i){ 
            mx=rad[i]+i; 
            id=i; 
        } 
    } 
} 
 
void cal_str(char str[],char s[],int rad[]){ 
    int i,len; 
    len=strlen(str); 
    s[0]='$'; 
    for(i=0;i<len;i++){ 
        s[2*i+1]='#'; 
        s[2*i+2]=str[i]; 
    } 
    s[2*len+1]='#'; 
    s[2*len+2]='\0'; 
    Manacher(rad,s,2*len+2); 
} 
 
void sea(){ 
    int l1,l2,i,j,t; 
    l1=strlen(s1); 
    l2=strlen(s2); 
    memset(dp,0,sizeof(dp)); 
    t=0; 
    for(i=1;i<l1;i++){ 
        for(j=1;j<l2;j++){ 
            if(s1[i]==s2[j]) 
                dp[i][j]=dp[i-1][j-1]+1; 
            int MIN=min(dp[i][j]-1,min(rad1[i],rad2[j])); 
            if(MIN>ans){ 
                ans=MIN; 
                start=t-ans/2; 
            } 
        } 
        if(s1[i]!='#') 
            t++; 
    } 
} 
 
int main(){ 
    int n,i; 
    scanf("%s",str1); 
    cal_str(str1,s1,rad1); 
    scanf("%s",str2); 
    cal_str(str2,s2,rad2); 
    ans=0,start=0; 
    sea(); 
    for(i=0;i<ans;i++) 
        printf("%c",str1[start+i]); 
    printf("\n"); 
}