大自然的帮运工
使用板子注意事项：
注意：
1.串是否全是小写字母
2.根节点为1
3.节点数不超过maxn
4.多组数据注意 清空
5.复杂度嘛。。。。。建树o(n*len)
前置知识:Trie树
需求：
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
输入n个模式串， 一个原串
输出结果： 原串中含有模式串的个数。
in：
6
abcd
cd
cd
cdac
aab
abcdac
out：
5
#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
struct kkk{
int son[26]; //一般是小写字母 所以26个
int flag; ///相同模式串出现次数 或者是标记
int fail; /// 失配指针
}trie[maxn]; // maxn 树节点数
int n, cnt; // n个模式串 初始根编号 1
string s; // 子串
//建字典树
void insert(string s){
int u = 1;
int len = s.length();
for (int i = 0; i < len;i++){
int v = s[i] - 'a';
if(!trie[u].son[v]){
trie[u].son[v] = ++cnt;
}
u = trie[u].son[v];
}
trie[u].flag++;
}
// 设置失配指针
// fail 当前字符串最长的后缀字符串 在Trie上的可以找到的编号
void getFail(){
for (int i = 0; i < 26;i++){
trie[0].son[i] = 1;
}
queue<int> q;
q.push(1);
// 失配
trie[1].fail = 0;
while(!q.empty()){
int fa = q.front();
//cout<<fa<<endl;
q.pop();
int fafail = trie[fa].fail;
for (int i = 0; i < 26;i++){
int v = trie[fa].son[i];
// 下面trie[v].fail = trie[fafail].son[i];
// 有点dp的味道
if(!v){
//fa没有该v节点 所以用他的最长后缀字符串
// 的儿子节点来代替他。
trie[fa].son[i] = trie[fafail].son[i];
continue;
}
trie[v].fail = trie[fafail].son[i];
q.push(v);
}
}
}
// 原串与模式串的 关系
int query(string s){
int u = 1, ans = 0;
int len = s.length();
// 这个循环也很好理解
// 其实就是两个位置 i是串的右边，现在找该串的左边的位置j
// 要求j到i是该模式串,那要怎么做呢，用前面的trie树和失配指针
// 当然对于每个i有很多个j嘛， 模式串又不止一个是吧
//
for (int i = 0; i < len;i++){
int v = s[i] - 'a';
int k = trie[u].son[v];
// while 模式串不止一个 所以有种关系是可以找出j
// 关系即是 k=trie[u].fail; 不断迭代 直至没得了
while(k>1 and trie[k].flag!=-1){
ans += trie[k].flag;
trie[k].flag = -1;
k = trie[k].fail;
}
u = trie[u].son[v];
}
return ans;
}
int main(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cnt = 1;
// Trie树 根节点是 1 ,什么都没有
// 类型头指针
cin >> n;
for (int i = 1; i <= n;i++){
cin >> s;
insert(s);
}
getFail();
cin >> s;
cout << query(s);
return 0;
}
TWO （板子）
in：
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
out：
4
aba
2
alpha
haha
需求：
1、求出现次数最多的次数
2、求出现次数最多的模式串
传送门
多组输入： 当n==0时退出。 注意每次用时clear清空
AC代码：
#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
struct kkk{
int son[26];
int flag; ///相同模式串出现次数
int fail; /// 失配指针
void clear(){
memset(son, 0, sizeof(son));
fail = flag = 0;
}
}trie[maxn];
int n, cnt,ans;
string s;
string a[200];
int vis[200];
void insert(string s,int num){
int u = 1;
int len = s.length();
for (int i = 0; i < len;i++){
int v = s[i] - 'a';
if(!trie[u].son[v]){
trie[u].son[v] = ++cnt;
}
u = trie[u].son[v];
}
// 存位置
trie[u].flag=num;
}
void getFail(){
for (int i = 0; i < 26;i++){
trie[0].son[i] = 1;
}
queue<int> q;
q.push(1);
trie[1].fail = 0;
while(!q.empty()){
int fa = q.front();
//cout<<fa<<endl;
q.pop();
int fafail = trie[fa].fail;
for (int i = 0; i < 26;i++){
int v = trie[fa].son[i];
if(!v){
trie[fa].son[i] = trie[fafail].son[i];
continue;
}
trie[v].fail = trie[fafail].son[i];
q.push(v);
}
}
}
int query(string s){
int u = 1, ans = 0;
int len = s.length();
for (int i = 0; i < len;i++){
int v = s[i] - 'a';
int k = trie[u].son[v];
while(k>1){
// 找到了模式串就对该串的vis++
if(trie[k].flag){
vis[trie[k].flag]++;
}
k = trie[k].fail;
}
u = trie[u].son[v];
}
return ans;
}
void clear(){
for (int i = 0; i <= cnt;i++){
trie[i].clear();
}
for (int i = 1; i <= n;i++){
vis[i] = 0;
}
cnt = 1;
ans = 0;
}
void solve(){
cnt = 1;
while(1){
scanf("%d",&n);
if(n==0)
break;
clear();
for (int i = 1; i <= n;i++)
{
cin >> a[i];
insert(a[i], i);
}
getFail();
cin >> s;
query(s);
for (int i = 1; i <= n;i++){
ans = max(vis[i], ans);
}
cout << ans<<endl;
for (int i = 1; i <= n;i++){
if(vis[i]==ans){
cout << a[i] << endl;
}
}
}
return ;
}
int main(){
freopen("in.txt", "r", stdin);
freopen("out.txt","w", stdout);
solve();
return 0;
}