AC自动机
cpp
int tr[N][26],cnt[N],ne[N],idx;
bool vis[N];
void insert(string &s){
int p=0;
for(int i=0;i<s.size();i++){
int v=s[i]-'a';
if(!tr[p][v])tr[p][v]=++idx;
p=tr[p][v];
}
cnt[p]++;
}
void build(){
queue<int> q;
for(int i=0;i<26;i++){
if(tr[0][i])q.push(tr[0][i]);
}
while(!q.empty()){
auto u=q.front();
q.pop();
for(int i=0;i<26;i++){
int &p=tr[u][i];
if(!p)p=tr[ne[u]][i];
else{
ne[p]=tr[ne[u]][i];
q.push(p);
}
}
}
}
int query(string &s){
int ans=0;
for(int i=0,j=0;i<s.size();i++){
int v=s[i]-'a';
j=tr[j][v];
int p=j;
while(p&&!vis[p]){
ans+=cnt[p];
vis[p]=1;
p=ne[p];
}
}
return ans;
}