SubString

题目

真是一道非常好的码农题，\(SAM+LCT\)

看到查询子串出现次数我们就能想到这是一个\(SAM\)

看到动态往后加入字符串我们就可以想到需要\(LCT\)来维护子树和

由于\(LCT\)并不是很方便维护子树，所以每次加入一个点的时候只需要把根到这个点的路径上的点权加一就好了

查询在\(SAM\)上匹配出位置，差一个单点权值就可以了

别忘了加入\(clone\)节点的时候要继承儿子的点权

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#define maxn 1200005
#define re register
#define LL long long
char S[3000005],opt[10];
std::string chars;
int Q,mask,ans,lst=1,cnt=1;
int tag[maxn],rev[maxn],fa[maxn],ch[maxn][2],s[maxn],st[maxn];
inline int nroot(int x) {return ch[fa[x]][1]==x||ch[fa[x]][0]==x;}
void Gets(int mask) {
    scanf("%s",S);
    chars=S;
    for (int j=0;j<chars.length();j++) {
        mask=(mask*131+j)%chars.length();
        char t=chars[j];
        chars[j]=chars[mask];
        chars[mask]=t;
    }
}
inline void pushdown(int x) {
    if(rev[x]) {
        if(ch[x][0]) rev[ch[x][0]]^=1,std::swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
        if(ch[x][1]) rev[ch[x][1]]^=1,std::swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
        rev[x]=0;
    }
    if(tag[x]) {
        if(ch[x][0]) s[ch[x][0]]+=tag[x],tag[ch[x][0]]+=tag[x];
        if(ch[x][1]) s[ch[x][1]]+=tag[x],tag[ch[x][1]]+=tag[x];
        tag[x]=0;
    }
}
inline void rotate(int x) {
    int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][k^1];
    if(nroot(y)) ch[z][ch[z][1]==y]=x;
    ch[x][k^1]=y,ch[y][k]=w;
    fa[w]=y,fa[y]=x,fa[x]=z;
}
inline void splay(int x) {
    int y=x,top=0;
    st[++top]=x;
    while(nroot(y)) st[++top]=fa[y],y=fa[y];
    while(top) pushdown(st[top--]);
    while(nroot(x)) {
        int y=fa[x];
        if(nroot(y)) rotate((ch[fa[y]][1]==y)^(ch[y][1]==x)?x:y);
        rotate(x);
    }
}
inline void access(int x) {
    for(re int y=0;x;y=x,x=fa[x])
        splay(x),ch[x][1]=y;
}
inline void makeroot(int x) {
    access(x);splay(x),rev[x]^=1;std::swap(ch[x][0],ch[x][1]);
}
inline void split(int x,int y) {
    makeroot(x);access(y);splay(y);
}
inline void link(int x,int y) {
    fa[x]=y;
}
inline void cut(int x,int y) {
    split(x,y);ch[y][0]=fa[x]=0;
}
struct Suffix_Automata {
    int len[maxn],fa[maxn],son[maxn][26];
    inline void ins(int c) {
        int p=++cnt,f=lst; lst=p;
        len[p]=len[f]+1;
        while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
        if(!f) {fa[p]=1;link(p,fa[p]);split(1,p);tag[p]++;s[p]++;return;}
        int x=son[f][c];
        if(len[f]+1==len[x]) {fa[p]=x;link(p,fa[p]);split(1,p);tag[p]++;s[p]++;return;}
        int y=++cnt;
        len[y]=len[f]+1,fa[y]=fa[x],cut(fa[x],x),fa[x]=fa[p]=y;
        link(x,fa[x]),link(p,fa[p]),link(y,fa[y]);
        splay(x);s[y]=s[x];
        for(re int i=0;i<26;i++) son[y][i]=son[x][i];
        while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
        split(1,p);tag[p]++;s[p]++;
    }
    inline void add() {
        Gets(mask);
        int len=chars.length();
        for(re int i=0;i<len;i++) ins(chars[i]-‘A‘);
    }
    inline int check() {
        Gets(mask);
        int len=chars.length();
        int now=1;
        for(re int i=0;i<len;i++) {
            now=son[now][chars[i]-‘A‘];
            if(!now) break;
        }
        if(!now) return 0;
        splay(now);return s[now];
    }
}SAM;
int main()
{
    scanf("%d",&Q);
    scanf("%s",S+1);
    int len=strlen(S+1);
    for(re int i=1;i<=len;i++) SAM.ins(S[i]-‘A‘);
    while(Q--) {
        scanf("%s",opt);
        if(opt[0]==‘A‘) SAM.add();
        else {
            ans=SAM.check();
            mask^=ans;
            printf("%d\n",ans);
        }
    }
    return 0;
}

SubString

原文：https://www.cnblogs.com/asuldb/p/10371328.html