AcWing 1282. 搜索关键词
原题链接
中等
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int K = 26;
const int N = 5e5+10;
int tr[N][26],idx,cnt[N];
int fail[N];
void insert(string s){
int p=0;
for(int i=0;s[i];i++){
int u =s[i]-'a';
if(!tr[p][u])tr[p][u]=++idx;
p = tr[p][u];
}
cnt[p]++;
}
void build(){
queue<int>q;
for(int i=0;i<K;i++)
if(tr[0][i])q.push(tr[0][i]);
while(q.size()){
int u =q.front();q.pop();
for(int i=0;i<K;i++){
int v = tr[u][i];
if(v) fail[v] = tr[fail[u]][i],q.push(v);
else tr[u][i] = tr[fail[u]][i];
}
}
}
int query(string s){
int ans=0;
for(int k=0,i=0;s[k];k++){
i = tr[i][s[k]-'a'];
for(int j=i;j&&~cnt[j];j =fail[j])
ans+=cnt[j],cnt[j]=-1;
}
return ans;
}
int n;
int main(){
int t;
cin>>t;
string s;
while(t--){
idx = 0;
memset(tr,0,sizeof tr);
memset(fail,0,sizeof fail);
memset(cnt,0,sizeof cnt);
cin>>n;
for(int i=0;i<n;i++){
cin>>s;
insert(s);
}
build();
cin>>s;
cout<<query(s)<<endl;
}
return 0;
}