CF1207G Indie Album

一道很有意思的AC自动机好题。

AC自动机的本质是记录了一棵字典树上所有字符串的所有后缀，所以这道题我们可以充分利用这个性质。

这道题与板子题的不同之处就在于：文本串在不停的变化，每次增加一个字符。

我们先来复习一下AC自动机模版题的流程

1. 遍历文本串的所有前缀。
2. 将所有是这个前缀的后缀的模式串出现次数+1。（即沿着fail指针一直走到根，沿途的所有节点都是符合条件的）

而对于这道题，因为文本串每次只会添加一个字符。所以我们在上一个文本串的基础上，加入以当前节点到根组成的字符串的贡献即可。

那这道题的解决方案就比较清晰了：

我们将字符串\(s\)定义为当前字典树节点到根的所有节点组成的字符串，文本串\(s\)对应的模式串出现次数的记为\(t[s]\)，将文本串\(s\)对应的答案记为\(ans[s]\)

1. 建出一个文本串组成的字典树。
2. 对字典树进行DFS，每走到一个节点，将所有为s后缀的字符串的出现次数\(t\)加1。
3. 记录答案\(ans[s]=t[s]\)。
4. DFS回溯时，将所有为s后缀的字符串的出现次数\(t\)减1。

因为所有字符串长度和\(T\)的大小关系，\(T^2\)算法是过不了的。但是因为累计答案是在\(fail\)指针构成的树，所以我们可以用数据结构来维护这个东西。复杂度变成了\(T\log T\)。

个人感觉这道题的关键在于利用AC自动机“求解单文本串问题时会遍历文本串的所有前缀”这个性质，从而求解特殊的多文本串问题。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define maxn (int)(4*1e5+1000)using namespace std;int ans[maxn],ch[maxn][30],tr[maxn][30],c[maxn],queue[maxn],n,m,now_insert,tcnt,acnt,fcnt,ver_tr[maxn],fail[maxn],size[maxn],id[maxn];//id指在ac自动机上的点在fail树上的编号bool is_end[maxn];char s[10];struct gg{ int lo,id,mod_ed;string add;//版本和询问的模式串,以及模式串结尾位置在AC自动机上的编号}query[maxn];vector
          
           tr_ver[maxn],fail_son[maxn];vector
           
            so[maxn];//记录每个版本的询问void change(int now,int num) { for(int i=now;i<=fcnt;i+=i&-i){c[i]+=num;}}int sum(int now) { int re=0;for(int i=now;i>=1;i-=i&-i){re+=c[i];}return re;}int insert_ac(string data) { int now=0; for(int i=0;i
            
             >query[i].add;query[i].mod_ed=insert_ac(query[i].add);query[i].id=i; so[query[i].lo].push_back(query[i]); } build_ac(); dfs1(0); dfs2(0,0); for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}
            
           
          
         
        
       
      
     
    

另外，记录一下本题的小故事：