题目概述

Generating Strings

解题报告

裸的回文自动机回退。

对于一个长度为 $len$ 的回文串，在 $s$ 中出现一次的权值为 $(N-len+1)\cdot26^{N-len}$ 。

对于每个节点记录 $sum_p$ 表示 $p$ 在 $fail$ 树上所有祖先的权值和，如果插入一个字符后停在了 $p$ ，那么就会获得 $sum_p$ 的权值。

为了防止暴力回退复杂度爆炸，需要记录转移数组。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=500000,maxt=1000000,maxi=26,MOD=1e9+7;

int te,N,m,n,pw[maxn+5];char s[maxt+5];
int pl,pb,son[maxt+5][maxi],qui[maxt+5][maxi],len[maxt+5],fai[maxt+5];
int sum[maxt+5],pos[maxt+5],si[maxt+5],who[maxt+5],ans;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
char getlwr() {char ch=readc();while (!islower(ch)) ch=readc();return ch;}
int reads(char *s){
    int len=0;char ch=getlwr();
    while (islower(ch)) s[++len]=ch,ch=readc();
    s[len+1]=0;return len;
}
struct fastO{
    int si;char buf[100000];
    fastO() {si=0;}
    inline void putc(char ch){
        if (si==100000) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    static int len=0,buf[100];
    if (x<0) putchar('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    fo.putc(ch);
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
inline int newnode() {pl++;for (int i=0;i<maxi;i++) son[pl][i]=qui[pl][i]=0;return pl;}
inline int val(int p) {return len[p]<=N?MUL(N-len[p]+1,pw[N-len[p]]):0;}
void Extend(int i){
    int c=s[i]-'a';if (i-len[pb]-1<1 || s[i-len[pb]-1]-'a'!=c) pb=qui[pb][c];
    who[i]=pb;
    if (!son[pb][c]){
        int u=newnode(),k=fai[pb];len[u]=len[pb]+2;
        if (s[i-len[k]-1]-'a'!=c) k=qui[k][c];k=son[k][c];
        for (int i=0;i<maxi;i++) qui[u][i]=qui[k][i];
        qui[u][s[i-len[k]]-'a']=k;fai[u]=k;son[pb][c]=u;
        sum[u]=ADD(sum[fai[u]],val(u));
    }
    pb=son[pb][c];ans=ADD(ans,sum[pb]);
    pos[i]=pb;si[i]=pl;
}
int main(){
    pw[0]=1;for (int i=1;i<=maxn;i++) pw[i]=MUL(pw[i-1],26);
    for (readi(te);te;te--){
        readi(N);readi(m);n=reads(s);
        pl=-1;newnode();newnode();
        fai[0]=fai[1]=1;len[0]=0;len[1]=-1;sum[0]=sum[1]=0;
        for (int i=0;i<maxi;i++) qui[0][i]=1;
        pb=0;pos[0]=pb;si[0]=pl;
        ans=0;for (int i=1;i<=n;i++) Extend(i);
        writei(ans);
        for (int t=1,tp;t<=m;t++){
            readi(tp);
            if (tp==2){
                ans=ADD(ans,MOD-sum[pos[n]]);
                if (si[n]>si[n-1]) son[who[n]][s[n]-'a']=0;
                n--;pb=pos[n];pl=si[n];
            } else s[++n]=getlwr(),Extend(n);
            writei(ans);
        }
    }
    return 0;
}