TLE
查看原帖
TLE
787424
Capoien_xie_bei_Chen楼主2023/8/6 00:15
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int cnt,tr[200005][26],kword[200005],nxt[200005];
void insert(string s){
int root=0;
for(int i=0;i<s.size();i++){
int id=s[i]-'a';
if(!tr[root][id]) tr[root][id]=++cnt;
root=tr[root][id];
}
kword[root]++;
}
void bfs(){
queue<int> q;
for(int i=0;i<26;i++){
if(tr[0][i]){
 nxt[tr[0][i]]=0;
 q.push(tr[0][i]);
}
}
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tr[now][i]){
nxt[tr[now][i]]=tr[nxt[now]][i];
q.push(tr[now][i]);
}
else tr[now][i]=tr[nxt[now]][i];
}
}
}
int find(string s){
int now=0,ans=0;
for(int i=0;i<s.size();i++){
now=tr[now][s[i]-'a'];
for(int j=now;j && kword[j]!=-1;j=nxt[j]){
ans+=kword[j];
kword[j]=-1;
}
}
return ans;
}
int main(){
int n;
string s;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
insert(s);
}
nxt[0]=0;
bfs();
string t;
cin>>t;
cout<<find(t)<<endl;
return 0;
}
2023/8/6 00:15
加载中...