字典树
类似一个找字符串相同前缀存不同的操作。就是利用已经出现过的字符或建立新节点存字符串。
举个例子：我们现在用 $app$，$add$，$bug$，$bus$，$good$，$go$ 六个单词来建一个字典树，效果如下（“$*$”表示字符串结束标志）。
根
/|\
/ | \
/ | \
a b g
/| | \
/ | | \
p d u o
| | |\ |\
p d s g o *
| | | | |
* * * * d
|
*我们来解释一下步骤。
第一步，插入 $app$。
根首先查找根节点，发现根节点没有 $a$ 节点的儿子，那么建立 $a$ 节点的儿子。
根
/
/
/
a 同样没有 $app$ 字符串后面的节点，依次建立。
根
/
/
/
a
/
/
p
|
p$app$ 字符串建立完了，这是要在结尾补上一个标志，表示有一个字符串在这里结束。也可以建立一个结构体，定义一个节点存在这里结束的字符串是第几个（前提是字符串各不相同，否则可以用链式前向星或其他方法来特殊处理了）。
根
/
/
/
a
/
/
p
|
p
|
*第二步：插入 $add$。
首先查找根节点，发现根节点有 $a$ 节点的儿子，那么直接进入到这个节点。
接着发现 $a$ 节点没有 $p$ 儿子的节点，依次建立节字符串后面的字符节点（当匹配一个字符串是，如果一个节点的儿子不能满足当前的字符，那么后面的字符就可以直接建节点了，因为建的新节点不会有子节点，所以会又建新节点，循环往复）。
根
/
/
/
a
/|
/ |
p d
| |
p d
| |
* *同理，插入 $bug$，$bus$，$good$ 三个字符串后，我们来模拟一下插入 $go$。
根
/|\
/ | \
/ | \
a b g
/| | \
/ | | \
p d u o
| | |\ |
p d s g o
| | | | |
* * * * d
|
*首先查找根节点，发现根节点有 $g$ 节点的儿子，那么直接进入到这个节点。
接着发现 $g$ 节点有了 $o$ 儿子节点，那么直接进入到这个节点。
$go$ 遍历完了，接着在这个节点上打一个结束标记即可。
根
/|\
/ | \
/ | \
a b g
/| | \
/ | | \
p d u o
| | |\ |\
p d s g o *
| | | | |
* * * * d
|
*如果带上标号：
根
/|\
/ | \
/ | \
a b g
/| | \
/ | | \
p d u o
| | |\ |\
p d s g o(6)
| | / \ |
(1)(2)(4) (3) d
|
(5)代码实现：
const int o_o=1e5+10;//数组大小
struct po{//字典树节点
int f_l;//失配指针
int s_n[26];//子节点（26个字母）
int e_d;//结束指针
}a_c[o_o];
void b_t(string s,int x){//建树
int l=s.length();//要建的字符串长度
int n_w=0;
for(int i=0;i<l;i++){//遍历每一位
if(a_c[n_w].s_n[s[i]-'a']==0){//如果没有这个节点
a_c[n_w].s_n[s[i]-'a']=++x_p;//建立这个节点
yv(x_p);//初始化这个节点（多测清空）
}
n_w=a_c[n_w].s_n[s[i]-'a'];//顺次往下找
}
a_c[n_w].e_d=x;//结束标记是哪个字符串
}
int main(){
for(int i=1;i<=n;i++){
cin>>s[i];//读入字符串
a_s[i].n_m=0;//多测清空
a_s[i].i_d=i;//存坐标（第几个答案）
b_t(s[i],i);//字符串建到字典树上
}
return 0;
}AC自动机
AC自动机是一种比较高级的处理字符串的方法。
这道题目，首先要建出字典树，然后处理失配指针（和 KMP 的失配指针(这篇博文中，我用 kmp 数组存的失配指针)原理相似），接着统计每个字符串出现的字数，输出即可。
建字典树不再赘述。
处理失配指针
string s[o_o];//存字符串
int x_p=0;//为字典树开辟的新节点赋予下标
void yv(int x){//清空字典树的某个节点
memset(a_c[x].s_n,0,sizeof a_c[x].s_n);
a_c[x].f_l=0;
a_c[x].e_d=0;
}
void g_f(){
queue<int>q;//存要找失配指针的节点
for(int i=0;i<26;i++){//遍历根节点每个儿子
if(a_c[0].s_n[i]!=0){//这个儿子存在
a_c[a_c[0].s_n[i]].f_l=0;//失配后回根节点
q.push(a_c[0].s_n[i]);//加入到队列中
}
}
while(!q.empty()){//判断节点是否找完
int u=q.front();//取队头元素
q.pop();//弹掉队头
for(int i=0;i<26;i++){//找当前节点所有儿子
if(a_c[u].s_n[i]!=0){//这个节点确实有儿子
a_c[a_c[u].s_n[i]].f_l=a_c[a_c[u].f_l].s_n[i];//这个节点的儿子的失配指针 指向 这个节点的失配指针指向的节点的儿子
//类似于 KMP 的失配指针存法
//换个想法：在原串找的时候是顺着一条子串走的，但是有可能有其他字串有相同的部分，失配指针就是用来串道的
//这样保证了原串只用跑一遍
q.push(a_c[u].s_n[i]);//新节点收入队列
}
else a_c[u].s_n[i]=a_c[a_c[u].f_l].s_n[i];//这个节点的失配指针指向的节点的儿子 是 这个节点的儿子
}
}
}失配指针主要作用还是“串道”和“KMP失配指针”。
能匹配到这一步，就已经有了匹配到这里的资格。
统计字符串在原串中出现的次数
注意判断字符串结束统计，及时换道。
失配指针也可以理解成邻接表相似的作用。
void f_a_c(string s){//统计字符串在原串中出现的次数
int l=s.length();//原串长度
int n_w=0;//初始化遍历节点下标
for(int i=0;i<l;i++){//每个字符都从字典树根找一遍
n_w=a_c[n_w].s_n[s[i]-'a'];//顺次往下找
for(int t=n_w;t;t=a_c[t].f_l)//直接跳到失配指针，类似于 KMP 的失配指针
a_s[a_c[t].e_d].n_m++;//如果是结束标记，因为已经标记了是哪个串的（见建字典树部分）所以直接统计 +1 即可。
}
}代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int r_r(){//快读
int x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e5+10;
struct po{
int f_l;//失配指针
int s_n[26];//子节点（26个字母）
int e_d;//结束指针
}a_c[o_o];
struct pp{
int n_m;//存字符串在
int i_d;//原串的下标
}a_s[o_o];
bool cmp(pp a,pp b){
return a.n_m==b.n_m?a.i_d<b.i_d:a.n_m>b.n_m;//多的靠前，一样多的按下标，小的靠前
}
string s[o_o];//存字符串
int x_p=0;//为字典树开辟的新节点赋予下标
void yv(int x){//清空字典树的某个节点
memset(a_c[x].s_n,0,sizeof a_c[x].s_n);
a_c[x].f_l=0;
a_c[x].e_d=0;
}
void b_t(string s,int x){//建树
int l=s.length();//要建的字符串长度
int n_w=0;
for(int i=0;i<l;i++){//遍历每一位
if(a_c[n_w].s_n[s[i]-'a']==0){//如果没有这个节点
a_c[n_w].s_n[s[i]-'a']=++x_p;//建立这个节点
yv(x_p);//初始化这个节点（多测清空）
}
n_w=a_c[n_w].s_n[s[i]-'a'];//顺次往下找
}
a_c[n_w].e_d=x;//结束标记是哪个字符串
}
void g_f(){
queue<int>q;//存要找适配指针的节点
for(int i=0;i<26;i++){//遍历根节点每个儿子
if(a_c[0].s_n[i]!=0){//这个儿子存在
a_c[a_c[0].s_n[i]].f_l=0;//失配后回根节点
q.push(a_c[0].s_n[i]);//加入到队列中
}
}
while(!q.empty()){//判断节点是否找完
int u=q.front();//取队头元素
q.pop();//弹掉队头
for(int i=0;i<26;i++){//找当前节点所有儿子
if(a_c[u].s_n[i]!=0){//这个节点确实有儿子
a_c[a_c[u].s_n[i]].f_l=a_c[a_c[u].f_l].s_n[i];//这个节点的儿子的失配指针 指向 这个节点的失配指针指向的节点的儿子
//类似于 KMP 的失配指针存法
//换个想法：在原串找的时候是顺着一条子串走的，但是有可能有其他字串有相同的部分，失配指针就是用来串道的
//这样保证了原串只用跑一遍
q.push(a_c[u].s_n[i]);//新节点收入队列
}
else a_c[u].s_n[i]=a_c[a_c[u].f_l].s_n[i];//这个节点的失配指针指向的节点的儿子 是 这个节点的儿子
}
}
}
void f_a_c(string s){//统计字符串在原串中出现的次数
int l=s.length();//原串长度
int n_w=0;//初始化遍历节点下标
for(int i=0;i<l;i++){//每个字符都从字典树根找一遍
n_w=a_c[n_w].s_n[s[i]-'a'];//顺次往下找
for(int t=n_w;t;t=a_c[t].f_l)//直接跳到失配指针，类似于 KMP 的失配指针
//同样一句话：既然匹配到这，就有匹配到这的资格
a_s[a_c[t].e_d].n_m++;//如果是结束标记，因为已经标记了是哪个串的（见建字典树部分）所以直接统计 +1 即可。
}
}
int main(){
while(1){//多测
int n=r_r();//子串的个数
if(!n)break;//多测终止条件
x_p=0;//多测清空
yv(0);//清空字典树根节点
for(int i=1;i<=n;i++){
cin>>s[i];//读入字符串
a_s[i].n_m=0;//多测清空
a_s[i].i_d=i;//存坐标（第几个答案）
b_t(s[i],i);//字符串建到字典树上
}
a_c[0].f_l=0;//初始化跟节点适配指针
g_f();//遍历失配指针
cin>>s[0];//读入要查询的串
f_a_c(s[0]);//找到每个子串在原串的出现次数
sort(a_s+1,a_s+1+n,cmp);//出现次数排序（按题目要求）
cout<<a_s[1].n_m<<endl;//输出出现最多的字符串出现了几次
cout<<s[a_s[1].i_d]<<endl;//按顺序输出
for(int i=2;i<=n;i++){
if(a_s[i].n_m==a_s[i-1].n_m)cout<<s[a_s[i].i_d]<<endl;//从大到小排的序。若不同，不符合条件
else break;
}
}
return 0;
}
