在Trie上做KMP
https://www.luogu.org/problemnew/show/3808
#include<cstdio>
#include<queue>
#include<iostream>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using std::cin;
const int N=4000011;
char s[N];
int tot,n,ans;
namespace AC_automaton{
struct Tire{
int cnt,fail;
int to[27];
}tr[N];
inline void build_tire(){
int u=0;
for(register int i=0;s[i]!=' ';++i){
if(!tr[u].to[s[i]-'a'])
tr[u].to[s[i]-'a']=++tot;
u=tr[u].to[s[i]-'a'];
}
++tr[u].cnt;
}
inline void build_automaton(){
int v,u;
std::queue<int>q;
FOR(i,0,25)
if((v=tr[0].to[i]))
q.push(v);
int now;
while(!q.empty()){
now=q.front();q.pop();
FOR(i,0,25){
v=tr[now].to[i];
u=tr[now].fail;
if(v){
tr[v].fail=tr[u].to[i];
q.push(v);
}
else
tr[now].to[i]=tr[u].to[i];
}
}
}
inline void match(){
int now=0,tmp;
for(register int i=0;s[i]!=' ';++i){
now=tr[now].to[s[i]-'a'];
tmp=now;
while(tmp&&tr[tmp].cnt!=-1){
ans+=tr[tmp].cnt;
tr[tmp].cnt=-1;
tmp=tr[tmp].fail;
}
}
}
}
using namespace AC_automaton;
int main(){
scanf("%d
",&n);
while(n--){
scanf("%s",s);
build_tire();
}
tr[0].fail=0;
build_automaton();
scanf("%s",s);
match();
printf("%d
",ans);
return 0;
}
https://www.luogu.org/problemnew/show/3796
#include<cstdio>
#include<queue>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
const int N=1000011;
std::queue<int>q;
namespace AC_automaton{
int ans[155];
char s[233][233];
char A[N];
struct Tire{
int fail;
int to[26];
int pos;
inline void init(){
fail=pos=0;
FOR(i,0,25)to[i]=0;
}
}tr[N];
int tot;
inline void insert(char *s,int pos){
int u=0,v;
for(register int i=0;s[i]!=' ';++i){
if(!tr[u].to[s[i]-'a'])
tr[tr[u].to[s[i]-'a']=++tot].init();
u=tr[u].to[s[i]-'a'];
}
tr[u].pos=pos;
}
inline void build_fail(){
int u,v,now;
FOR(i,0,25)
if((u=tr[0].to[i])){
tr[u].fail=0;
q.push(u);
}
while(!q.empty()){
now=q.front();q.pop();
FOR(i,0,25){
v=tr[now].to[i];
u=tr[now].fail;
if(v){
tr[v].fail=tr[u].to[i];
q.push(v);
}
else
tr[now].to[i]=tr[u].to[i];
}
}
}
inline void match(char *s){
int now=0,tmp;
for(register int i=0;s[i]!=' ';++i){
now=tr[now].to[s[i]-'a'];
tmp=now;
while(tmp){
++ans[tr[tmp].pos];
tmp=tr[tmp].fail;
}
}
}
}
using namespace AC_automaton;
int n,mx;
int main(){
while(~scanf("%d",&n)&&n){
FOR(i,0,n)
ans[i]=0;
tot=0;
tr[0].fail=0;
tr[0].init();
FOR(i,1,n){
scanf("%s",s[i]);
insert(s[i],i);
}
build_fail();
scanf("%s",A);
match(A);
ans[0]=0;
mx=1;
FOR(i,1,n)
if(ans[mx]<ans[i])
mx=i;
printf("%d
",ans[mx]);
FOR(i,1,n)
if(ans[mx]==ans[i])
printf("%s
",s[i]);
}
return 0;
}