本文主要是介绍Trie字典树和AC自动机(题目),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
A. 三年二班的投票
题目描述:
三年级二班已经完成了竞选班长的投票,已知一共有 n 张投票,每张投票上写了一位同学的名字。
投票统计结束后,张老师随意问一个同学的名字,请编程快速检索出,该同学共有几票。
输入:
第一行读入一个整数 n ,代表产生了 n 张投票。( n≤10^5 )
接下来 n 行,每行有一个字符串 s ,代表该张投票上写的同学的姓名(姓名由不含空格的小写英文字母组成,n 个姓名的总长度 ≤10^6 。
接下来一行读入一个整数 m( m≤10^5 ),代表王老师提问的同学的姓名数量。
接下来 m 行,每行有一个字符串 t ,代表每次询问的姓名;(姓名由不含空格的小写英文字母组成,m 个姓名的总长度 ≤10^6 )。
输出:
输出 m 行,第 i 行输出第 i 次询问的姓名,在投票中出现的总次数。
样例:
输入:
5 lihua zhaoxiang wangfang lihua zhangxiang 3 lihua wangfang sunming
输出:
2 1 0
代码如下:
#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
//下标为0的行,表示根,也表示空节点
int ch[N][26];//字典树
//cnt:以第i个字母结尾的单词有多少个
int cnt[N],idx;
char s[N];//每次读入的名字
int n,m;//建字典树
void insert(char s[]){int p = 0;//从下标为0的行开始for(int i = 0;s[i];i++){int u = s[i] - 'a';//转换为0~25//如果p节点不存在u这个子结点,则创建子结点 if(!ch[p][u]) ch[p][u] = ++idx;p = ch[p][u];} cnt[p]++;//结束,以第p个字母结尾的字符串数量+1
} //查询:返回字符串出现的次数
int query(char s[]){int p = 0;for(int i = 0;s[i];i++){int u = s[i] - 'a';if(!ch[p][u]) return 0;//没有出现p = ch[p][u]; }return cnt[p];
}int main(){scanf("%d",&n);while(n--){scanf("%s",s);insert(s);}scanf("%d",&m);while(m--){scanf("%s",s);printf("%d\n",query(s));}return 0;
}
B. 数字串前缀匹配
题目描述:
给定 n 个长度不超过 10 的数字串,问其中是否存在两个数字串 S,T,使得 S 是 T 的前缀。
本题读入多组数据,请对每组数据进行计算并输出结果。(数据组数≤40,n≤10^4)
输入:
第一行一个整数 T,表示数据组数。
对于每组数据,第一行一个数 n,接下来 n 行输入 n 个数字串。
输出:
对于每组数据,若存在两个数字串 S,T,使得 S 是 T 的前缀,则输出 NO
,否则输出 YES
。
样例:
输入:
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
输出:
NO YES
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int ch[N][10];
int cnt[N];
char s[20];
int n,T,idx;
bool insert(char s[]){bool f1=0;bool f2=0;int p=0;for(int i=0;s[i];i++){int x=s[i]-'0';if(!ch[p][x]) ch[p][x]=++idx,f1=1;p=ch[p][x];if(cnt[p]!=0) f2=1;}cnt[p]++;return (f1==0)||f2;
}
int query(char s[]){int p=0;for(int i=0;s[i];i++){int x=s[i]-'a';if(!ch[p][x]) return 0;p=ch[p][x];}return cnt[p];
}
int main(){scanf("%d",&T);while(T--){memset(ch,0,sizeof(ch));memset(cnt,0,sizeof(cnt));idx=0;scanf("%d",&n);bool f=0;while(n--){scanf("%s",s);if(insert(s)) f=1;}if(f) printf("NO\n");else printf("YES\n");}return 0;
}
C. 关键词搜索
题目描述:
给定 n 个长度不超过 50 的由小写英文字母组成的单词准备查询,以及一篇长为 m 的文章,问:文中出现了多少个待查询的单词。多组数据。
输入:
第一行一个整数 T,表示数据组数;
对于每组数据,第一行一个整数 n,接下去 n 行表示 n 个单词,最后一行输入一个字符串(不含空格),表示文章。(对于全部数据,1≤n≤104,1≤m≤106 。)
输出:
对于每组数据,输出一个数,表示文中出现了多少个待查询的单词(注意:同一个单词在文章中出现多次,也只算一次)。
样例:
输入:
1 5 she he say shr her yasherhs
输出:
3
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e6+10,L=55;
int ch[N*L][26];
int cnt[N*L],ne[N*L],q[N*L];
char w[L],s[M];
int n,T,idx;
void init(){memset(ch,0,sizeof(ch));memset(cnt,0,sizeof(cnt));idx=0;memset(ne,0,sizeof(ne));
}
void bfs(){int h=1,t=0;for(int i=0;i<26;i++){if(ch[0][i]) q[++t]=ch[0][i];}while(h<=t){int f=q[h];for(int i=0;i<26;i++){if(ch[f][i]){int c=ch[f][i];int j=ne[f];while(j&&!ch[j][i]){j=ne[j];}if(ch[j][i]) j=ch[j][i];ne[c]=j;q[++t]=c;}}h++;}
}
void insert(char w[]){int p=0;for(int i=0;w[i];i++){int x=w[i]-'a';if(!ch[p][x]) ch[p][x]=++idx;p=ch[p][x];}cnt[p]++;
}
int main(){scanf("%d",&T);while(T--){init();scanf("%d",&n);while(n--){scanf("%s",w);insert(w);}bfs();scanf("%s",s);int res=0;for(int i=0,j=0;s[i];i++){int x=s[i]-'a';while(j&&!ch[j][x]) j=ne[j];if(ch[j][x]) j=ch[j][x];int p=j;while(p!=0){res+=cnt[p];cnt[p]=0;p=ne[p];}}printf("%d\n",res);}return 0;
}
这篇关于Trie字典树和AC自动机(题目)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!