两道差不多的题，都是回文自动机right集合处理相关。

APIO2014 回文串

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。

数据满足1≤字符串长度≤300000。

题解

co int N=300000+10;
int last=1,tot=1;
int ch[N][26],fa[N]={1,1},len[N]={0,-1},siz[N];
char s[N];

int get_fa(int x,int i){
    while(s[i-len[x]-1]!=s[i]) x=fa[x];
    return x;
}
void extend(int i){
    int p=get_fa(last,i);
    int x=ch[p][s[i]-'a'];
    if(!x){
        x=++tot;
        fa[x]=ch[get_fa(fa[p],i)][s[i]-'a'];
        len[x]=len[p]+2;
        ch[p][s[i]-'a']=x;
    }
    ++siz[x];
    last=x;
}
int main(){
    scanf("%s",s+1);int n=strlen(s+1);
    for(int i=1;i<=n;++i) extend(i);
    for(int i=tot;i>=2;--i) siz[fa[i]]+=siz[i];
    LL ans=0;
    for(int i=1;i<=tot;++i) ans=max(ans,(LL)siz[i]*len[i]);
    printf("%lld\n",ans);
    return 0;
}

Victor and String

Victor loves to play with string. He thinks a string is charming as the string is a palindromic string.

Victor wants to play n times. Each time he will do one of following four operations.

1. add a char c to the beginning of the string.

2. add a char c to the end of the string.

3. ask the number of different charming substrings.

4. ask the number of charming substrings, the same substrings which starts in different location has to be counted.

At the beginning, Victor has an empty string.

1≤n≤100000

题解

来自翁文涛《回文树及其应用》。

CO int N=200000+10;

namespace PAM{
    int str[N],L,R;
    int tot,last[2];
    int ch[N][26],fa[N],len[N],dep[N];
    LL ans;
    
    IN int new_node(int l){
        fill(ch[tot],ch[tot]+26,0);
        len[tot]=l,dep[tot]=0;
        return tot++;
    }
    IN void init(int n){
        memset(str,-1,sizeof str),L=n,R=n-1;
        tot=0,new_node(0),new_node(-1),fa[0]=fa[1]=1;
        last[0]=last[1]=1;
        ans=0;
    }
    int get_fail(int x,bool d){
        if(d)while(str[R-len[x]-1]!=str[R]) x=fa[x];
        else while(str[L+len[x]+1]!=str[L]) x=fa[x];
        return x;
    }
    void extend(int c,bool d){
        if(d) str[++R]=c;
        else str[--L]=c;
        int p=get_fail(last[d],d);
        if(!ch[p][c]){
            int cur=new_node(len[p]+2);
            fa[cur]=ch[get_fail(fa[p],d)][c];
            ch[p][c]=cur;
            dep[cur]=dep[fa[cur]]+1;
        }
        last[d]=ch[p][c];
        if(len[last[d]]==R-L+1) last[d^1]=last[d];
        ans+=dep[last[d]];
    }
}

void real_main(int n){
    PAM::init(n);
    while(n--){
        int opt=read<int>();
        if(opt<=2){
            char c[2];scanf("%s",c);
            PAM::extend(c[0]-'a',opt-1);
        }
        else if(opt==3) printf("%d\n",PAM::tot-2);
        else if(opt==4) printf("%lld\n",PAM::ans);
    }
}
int main(){
    for(int n;~scanf("%d",&n);) real_main(n);
    return 0;
}

我发现初始化的时候必须memset。这是因为跳fail的时候可能会越界。

然后我加了一些特判，可以去掉memset。

namespace PAM{
    int str[N],L,R;
    int tot,last[2];
    int ch[N][26],fa[N],len[N],dep[N];
    LL ans;
    
    IN int new_node(int l){
        fill(ch[tot],ch[tot]+26,0);
        len[tot]=l,dep[tot]=0;
        return tot++;
    }
    IN void init(int n){
        L=n,R=n-1;
        tot=0,new_node(0),new_node(-1),fa[0]=fa[1]=1;
        last[0]=last[1]=1;
        ans=0;
    }
    int get_fail(int x,bool d){
        if(d)while(assert(L<=R-len[x]-1 and R-len[x]-1<=R),str[R-len[x]-1]!=str[R]) x=fa[x];
        else while(assert(L<=L+len[x]+1 and L+len[x]+1<=R),str[L+len[x]+1]!=str[L]) x=fa[x];
        return x;
    }
    void extend(int c,bool d){
        if(d) str[++R]=c;
        else str[--L]=c;
        int p=get_fail(len[last[d]]==R-L?fa[last[d]]:last[d],d); // edit
        if(!ch[p][c]){
            int cur=new_node(len[p]+2);
            fa[cur]=ch[get_fail(fa[p],d)][c];
            ch[p][c]=cur;
            dep[cur]=dep[fa[cur]]+1;
        }
        last[d]=ch[p][c];
        if(len[last[d]]==R-L+1) last[d^1]=last[d];
        ans+=dep[last[d]];
    }
}

APIO2014 回文串 和 HDU5421 Victor and String