hdu7192,巧用sam

AC/DC

题目传送门

前言

这是2022hdu多校第5场的1008，当时因为通过率过低，题目都没看，结束后看了之后发现是道 $SAM$ 好题，在这里补一下。

题目大意

给出一个初始字符串 $s$ ，有三种操作

• $1\ c$ : 在 $s$ 的末尾加上一个字符 $c$ 。
• $2$ : 删掉 $s$ 的最前面的那个字符。
• $3\ t$ : 这里 $t$ 是一个字符串，表示询问字符串 $t$ 在当前的 $s$ 中出现多少次，即询问当前的 $s$ 中有多少个子串 $t$ 。

$T(1 \leq T \leq 5)$ 组样例，初始长度为 $n(1 \leq n \leq 10^5)$ ，操作数量为 $m(1 \leq m \leq 10^5)$ 。

强制在线。

大致思路

看完题之后很容易能够想到 $SAM$ ，可以非常有效的进行查询。

但是这道题的操作数过多。朴素使用 $SAM$ 会造成超时。

于是我们想到使用定期重构的思路。

设 $T=\sqrt n$ ，每 $T$ 次添加或删除字符操作后，就重构 $SAM$ 。对于还没有来得及重构的询问，我们使用字符串 $Hash$ 来进行解决。

对于计数，我们在每次重构 $SAM$ 之后进行一次 $dfs$ 即可更新。

代码

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

struct SamNode{
    int ch[26];
    int len,fa;
    SamNode(){memset(ch,0,sizeof(ch));len=0;}
}sam[MAXX<<2];
int las=1,sam_cnt=1;

LL num[MAXX<<2];
void add(int c){
    int p=las;int np=las=++sam_cnt;
    num[np]=1LL;//此行为计数用，标记出现过几次 
    sam[np].len=sam[p].len+1;
    for(;p&&!sam[p].ch[c];p=sam[p].fa) sam[p].ch[c]=np;
    if(!p) sam[np].fa=1;
    else{
        int q=sam[p].ch[c];
        if(sam[q].len==sam[p].len+1) sam[np].fa=q;
        else{
            int nq=++sam_cnt;sam[nq]=sam[q];
            sam[nq].len=sam[p].len+1;
            sam[q].fa=sam[np].fa=nq;
            for(;p&&sam[p].ch[c]==q;p=sam[p].fa) sam[p].ch[c]=nq;
        }
    }
}
vector<int> to[MAXX<<2];
void dfs(int now){
    for(int jj:to[now]){
        dfs(jj);
        num[now]+=num[jj];
    }
}


int m,l,r,lasl,lasr;
char s[MAXX<<1],a[MAXX];
typedef unsigned long long ull;
//prim 是自己设置的一个素数,具体数值根据情况而定
ull p[MAXX<<1],hashs[MAXX<<1],prim=233;

inline void init(){
    p[0]=1ull;
    int maxx=MAXX<<1;
    for(int i=1;i<maxx;++i)
        p[i]=p[i-1]*prim;
}
inline ull gethash(int l,int r){
    return hashs[r]-hashs[l-1]*p[r-l+1];
}
inline bool check(int l,int r,ull jj){
    return gethash(l,r)==jj;
}

inline void build(){
    for(int i=1;i<=sam_cnt;++i){
        sam[i]=SamNode();
        to[i].clear();
        num[i]=0LL;
    }
    las=sam_cnt=1;
    for(int i=l;i<=r;++i)
        add(s[i]-'a');
    lasl=l;lasr=r;

    for(int i=1;i<=sam_cnt;++i)
        to[sam[i].fa].emplace_back(i);
    dfs(1);
    num[0]=num[1]=0;
}

int getans(int len){
    int ans=0,now=1;
    for(int i=1;i<=len;++i){
        now=sam[now].ch[a[i]-'a'];
    }
    ans=num[now];
    ull hasha=0LL;
    for(int i=1;i<=len;++i)
        hasha=hasha*prim+a[i];
    for(int i=lasl;i<l&&i+len-1<=lasr;++i){
        if(check(i,i+len-1,hasha))
            --ans;
    }
    for(int i=lasr+1;i<=r&&i-len+1>=l;++i){
        if(check(i-len+1,i,hasha))
            ++ans;
    }

    return ans;
}

inline void solve(){
    getchar();scanf("%s",s+1);
    l=1;r=strlen(s+1);
    for(int i=l;i<=r;++i)
        hashs[i]=hashs[i-1]*prim+s[i];
    build();
    scanf("%d",&m);
    int lastans=0,changed=0,rebuild=4000;
    while(m--){
        int cho;scanf("%d",&cho);
        if(cho==1){
            char ch;
            getchar();scanf("%c",&ch);
            ch=((ch-'a')^lastans)%26+'a';
            s[++r]=ch;
            hashs[r]=hashs[r-1]*prim+s[r];
            ++changed;
        }
        else if(cho==2){
            ++l;++changed;
        }
        else{
            getchar();scanf("%s",a+1);
            int len=strlen(a+1);
            for(int i=1;i<=len;++i)
                a[i]=((a[i]-'a')^lastans)%26+'a';
            
            if(changed>=rebuild){
                build();
                changed=0;
            }
            if(r==l-1){
                lastans=0;
                printf("%d\n",lastans);
                continue;
            }
            lastans=getans(len);
            // printf("%s\n",a+1);
            printf("%d\n",lastans);
        }
    }
    
    
}

signed main(){
    init();
    LL t;scanf("%lld",&t);
    while(t--)
        solve();
    
    return 0;
}

总结

一般这种定期重构的代码量会比较大，非常容易出错，要耐下心来认真写。

对于 $T$ 的取值，这道题的数据量是 $10^5$ ，我们取 $T=4000$ 。