#include <bits/stdc++.h>
using namespace std;
const int maxlen = 1000010;
namespace Trie{
struct node{
int fail,cnt,nxt['z'-'a'+2];
node(){memset(nxt,0,sizeof nxt);}
}trie[maxlen];
int tid = 0;
void insert(int id,char *str){
int len = strlen(str);
for(int i=0;i<len;i++){
int now = str[i] - 'a';
if(trie[id].nxt[now] == 0){
//new node
trie[id].nxt[now] = ++tid;
}
id = trie[id].nxt[now];
}
trie[id].cnt++;
}
}
namespace ACAuto{
void getFail(int id){
queue<int> q;
for(char c='a';c<='z';c++){
int now = Trie::trie[id].nxt[c-'a'];
if(now){
q.push(now);
Trie::trie[id].fail = id;
}
}
while(!q.empty()){
int u = q.front();
q.pop();
for(char c='a';c<='z';c++){
int v = Trie::trie[u].nxt[c-'a'];
if(!v) {
Trie::trie[u].nxt[c-'a'] = Trie::trie[Trie::trie[u].fail].nxt[c-'a'];
continue;
}
Trie::trie[v].fail = Trie::trie[Trie::trie[u].fail].nxt[c-'a'];
q.push(v);
}
}
}
long long query(int id,char *str){
long long ans = 0;
int len = strlen(str);
for(int i=0;i<len;i++){
int now = Trie::trie[id].nxt[str[i]-'a'];
while(now && Trie::trie[now].cnt != -1){
ans += Trie::trie[now].cnt;
Trie::trie[now].cnt = -1;
now = Trie::trie[now].fail;
}
id = Trie::trie[id].nxt[str[i]-'a'];
}
return ans;
}
}
int n;
char tmp[maxlen];
int main(){
//freopen("testdata.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",tmp);
Trie::insert(0,tmp);
}
ACAuto::getFail(0);
scanf("%s",tmp);
printf("%lld\n",ACAuto::query(0,tmp));
return 0;
}
[模板]AC自动机
2019-04-01 19:36:26