AC自动机
<pre><code>#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int maxn = 1e6+5;
int tree[maxn][27];
int cnt[maxn];
int fail[maxn];
queue<int> que;
int cnts = 0;
void insert(const string &str){
int root = 0;
for(int i = 0; str[i] != '\0'; i++){
int now = str[i] - 'a'; //!!!!!!
if(!tree[root][now]){
tree[root][now] = cnts++;
}
root = tree[root][now];
}
cnt[root]++;
return;
}
void getfail(){
for(int i = 0; i + 'a' <= 'z'; i++){ //!!!!!!
if(tree[0][i]){
fail[tree[0][i]] = 0;
que.push(tree[0][i]);
}
}
while(que.size()){
int now = que.front();
que.pop();
for(int i = 0; i + 'a' <= 'z'; i++){ //!!!!!!!
if(tree[now][i]){
fail[tree[now][i]] = tree[fail[now]][i];
que.push(tree[now][i]);
}
else{
tree[now][i] = tree[fail[now]][i];
}
}
}
return;
}
int query(const string &str){
int now = 0, ans = 0;
for(int i = 0; str[i] != '\0'; i++){
now = tree[now][str[i]-'a']; //!!!!!!!!
for(int j = now; j && cnt[j] != -1; j = fail[j]){
ans += cnt[j];
cnt[j] = -1;
}
}
return ans;
}</code></pre>