Solution CF710F String Set Queries
题目大意：你需要维护一个字符串集合，支持插入一个字符串，删除一个字符串，查询集合中的所有字符串在给出的模板串中出现的总次数。
AC自动机、二进制分组
分析：
首先此题加减字符串，可以变成对询问贡献的正负，这样修改操作对询问的贡献之间是互不影响的，因此可以考虑二进制分组，或者根号重构AC自动机。
但这题教会我AC自动机上不能暴力跳fail找所有匹配的文本串，这样的复杂度是错误的。（鬼知道为啥之前跑的飞快哇）
注意到将Trie树补全成Trie图之后，每次走到一个位置，对答案会有fail链上的权值和的贡献。因此反向连fail指针建立一棵fail树，预处理出根到每个点路径上的点的权值和即可
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxdep = 32;
struct Aho{
static const int maxnode = 1e5 + 1000,sigma = 26;
int ch[maxnode][sigma],val[maxnode],fail[maxnode],tot,dfn[maxnode],siz[maxnode],dis[maxnode],dfs_tot;
vector<pair<string,int>> vec;
vector<int> G[maxnode];
inline void addedge(int u,int v){G[u].push_back(v);}
inline int idx(char c){return c - 'a';}
inline void dfs(int u){
siz[u] = 1;
dfn[u] = ++dfs_tot;
for(int v : G[u]){
dis[v] = dis[u] + val[v];
dfs(v);
siz[u] += siz[v];
}
}
inline void clear(){
vec.clear();
for(int i = 0;i <= tot;i++){
memset(ch[i],0,sizeof(ch[i]));
val[i] = fail[i] = dfn[i] = siz[i] = dis[i] = 0;
G[i].clear();
}
tot = dfs_tot = 0;
}
inline int newnode(){return ++tot;}
inline void insert(const string &str,int v){
int u = 0;
for(auto x : str){
int c = idx(x);
if(!ch[u][c])ch[u][c] = newnode();
u = ch[u][c];
}
val[u] += v;
vec.push_back(make_pair(str,v));
}
inline void build(){
queue<int> q;
for(int i = 0;i < sigma;i++)
if(ch[0][i])q.push(ch[0][i]);
while(!q.empty()){
int u = q.front();q.pop();
for(int c = 0;c < sigma;c++)
if(ch[u][c])fail[ch[u][c]] = ch[fail[u]][c],q.push(ch[u][c]);
else ch[u][c] = ch[fail[u]][c];
}
for(int i = 1;i <= tot;i++)
addedge(fail[i],i);
dfs(0);
}
inline ll query(const string &str){
int u = 0;
ll res = 0;
for(auto x : str){
int c = idx(x);
u = ch[u][c];
res += dis[u];
}
return res;
}
}ac[maxdep];
vector<pair<string,int>> vec;
int q,top;
inline void modify(const string &str,int v){
top++;
ac[top].insert(str,v);
ac[top].build();
while(ac[top].vec.size() == ac[top - 1].vec.size()){
vec.clear();
for(auto x : ac[top].vec)vec.push_back(x);
for(auto x : ac[top - 1].vec)vec.push_back(x);
ac[top].clear();
ac[top - 1].clear();
top--;
for(auto x : vec)ac[top].insert(x.first,x.second);
ac[top].build();
}
}
inline ll query(const string &str){
ll res = 0;
for(int i = 1;i <= top;i++)res += ac[i].query(str);
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> q;
for(int opt,i = 1;i <= q;i++){
static string str;
cin >> opt >> str;
if(opt == 1)modify(str,1);
else if(opt == 2)modify(str,-1);
else cout << query(str) << endl;
}
return (0-0);
}