ac自动机(简单)
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans;
string s,ss,t;//s是要匹配的串,t是文本
struct _node{
int fail;
int vis[26];
int end;//有几个匹配串以该结点结尾
}node[1000001];
queue<int> bfs;//构建fail指针是的bfs队列
void build()//trie
{
cin>>n;
int u=1;
int tot=1;
for(int i=1;i<=n;i++)
{
cin>>s;
ss=' '+s;
int len=s.size();
for(int j=1;j<=len;j++)
{
int c=ss[i]-'a';
if(!node[u].vis[c]) node[u].vis[c]=++tot;
u=node[u].vis[c];
}
node[u].end++;
}
cin>>t;
return;
}
void query()//构建fail指针
{
int u=1;
bfs.push(1);
for(int i=0;i<26;i++)
node[0].vis[i]=1;
while(!bfs.empty())
{
u=bfs.front();
bfs.pop();
for(int i=0;i<=25;i++)
{
if(!node[u].vis[i]) node[u].vis[i]=node[node[u].fail].vis[i];
else{
bfs.push(node[u].vis[i]);
int v=node[u].fail;
while(v>0&&!node[v].vis[i]) v=node[v].fail;
node[node[u].vis[i]].fail=node[v].vis[i];
}
}
}
return;
}
void pipei()
{
int u=1;
int c;
int k;
ss=' '+t;
int len=t.size();
for(int i=1;i<=len;i++)
{
c=ss[i]-'a';
k=node[u].vis[c];
while(k>1)
{
ans+=node[u].end;
node[u].end=0;
k=node[u].fail;
}
u=node[u].vis[c];
}
return;
}
int main(){
build();
query();
pipei();
cout<<ans;
}
输完数据就卡住了,光标在闪但是出不了答案。