SPOJ

Luogu

分析

首先思路肯定就是建 SAM，询问就找到对应位置然后求 $size$。

然而我们要支持插入，也就是要动态维护 $size$。

可以用 LCT 维护 Parent 树，每次相当于求子树和，用维护子树信息那一套即可。当然也可以直接链修改。

代码

我的写法可能有点奇怪 /kel

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=160000+10;

int n,Q; char s[N];


namespace L { // LCT
#define ls(o) ch[o][0]
#define rs(o) ch[o][1]

    int fa[N],ch[N][2],sz[N],vsz[N],w[N];
    bool nroot(int x) { return ls(fa[x])==x||rs(fa[x])==x; }
    void pushup(int x) { sz[x]=sz[ls(x)]+sz[rs(x)]+vsz[x]+w[x]; }

    void rotate(int x) {
        int y=fa[x],z=fa[y],k=x==rs(y),w=ch[x][!k];
        if (nroot(y)) ch[z][y==rs(z)]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    void splay(int x) {
        while (nroot(x)) {
            int y=fa[x],z=fa[y];
            if (nroot(y)) rotate((x==ls(y))^(y==ls(z))?x:y);
            rotate(x);
        }
        pushup(x);
    }

    void access(int x) {
        for (int y=0;x;x=fa[y=x])
            splay(x),vsz[x]+=sz[rs(x)]-sz[y],rs(x)=y,pushup(x);
    }
    void link(int x,int y) {
        splay(y),access(x),splay(x);
        fa[y]=x,vsz[x]+=sz[y],sz[x]+=sz[y];
    }
    void cut(int x,int y) {
        access(y),splay(y),ls(y)=fa[x]=0,pushup(y);
    }

#undef ls
#undef rs
}

namespace H { // SAM
    int lst,tot;
    int fa[N],ch[N][26],len[N];
    void extend(int c) {
        int p=lst,np=++tot; lst=np,len[np]=len[p]+1,L::w[np]=L::sz[np]=1;
        for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
        if (!p) fa[np]=1,L::link(1,np);
        else {
            int q=ch[p][c];
            if (len[p]+1==len[q]) fa[np]=q,L::link(q,np);
            else {
                int nq=++tot; len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],L::link(fa[nq],nq);
                L::cut(fa[q],q),fa[q]=fa[np]=nq,L::link(nq,q),L::link(nq,np);
                for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
    }
    int query(char *s,int l) {
        int p=1;
        for (int i=1;i<=l;++i) {
            if (!ch[p][s[i]-'a']) return 0;
            p=ch[p][s[i]-'a'];
        }
        L::splay(p); return L::sz[p]-L::sz[L::ch[p][0]];
    }
}

int main() {
    scanf("%s",s+1); n=strlen(s+1);
    H::lst=H::tot=1;
    for (int i=1;i<=n;++i) H::extend(s[i]-'a');
    Q=read(); int A=read(),B=read();
    while (Q--) {
        scanf("%s",s+1); int l=strlen(s+1);
        int ans=H::query(s,l); printf("%d\n",ans);
        H::extend((A*ans+B)%26);
    }
    return 0;
}