A. 三年二班的投票
题目描述
三年级二班已经完成了竞选班长的投票，已知一共有 n 张投票，每张投票上写了一位同学的名字。
投票统计结束后，张老师随意问一个同学的名字，请编程快速检索出，该同学共有几票。
输入
第一行读入一个整数 n ，代表产生了 n 张投票。（ n≤）
接下来 n 行，每行有一个字符串 s ，代表该张投票上写的同学的姓名（姓名由不含空格的小写英文字母组成，n 个姓名的总长度 ≤ ）。
接下来一行读入一个整数 m（ m≤ ），代表王老师提问的同学的姓名数量。
接下来 m 行，每行有一个字符串 ttt ，代表每次询问的姓名；（姓名由不含空格的小写英文字母组成，m 个姓名的总长度 ≤ ）。
输出
输出 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≤）
输入
第一行一个整数 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],cnt[N],idx = 0;
char s[20];
int T,n;
bool insert(char s[]){
bool f1 = false,f2 = false;
int p = 0;
for(int i = 0;s[i];i++){
int x = s[i] - '0';
if(!ch[p][x])ch[p][x] = ++idx,f1 = true;
p = ch[p][x];
if(cnt[p] != 0)f2 = true;
}
cnt[p]++;
return (f1==false) || f2;
}
int main(){
scanf("%d",&T);
while(T--){
memset(ch,0,sizeof(ch));
memset(cnt,0,sizeof(cnt));
idx = 0;
scanf("%d",&n);
bool f = false;
while(n--){
scanf("%s",s);
if(insert(s))f = true;
}
if(f)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
} C. 关键词搜索
题目描述
给定 n 个长度不超过 50 的由小写英文字母组成的单词准备查询，以及一篇长为 m 的文章，问：文中出现了多少个待查询的单词。多组数据。
输入
第一行一个整数 T，表示数据组数；
对于每组数据，第一行一个整数 n，接下去 n 行表示 n 个单词，最后一行输入一个字符串（不含空格），表示文章。（对于全部数据，1≤n≤,1≤m≤
。）
输出
对于每组数据，输出一个数，表示文中出现了多少个待查询的单词（注意：同一个单词在文章中出现多次，也只算一次）。
样例
输入：
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],cnt[N*L],idx = 0;
int ne[N*L];
int q[N*L];
char w[L],s[M];
int T,n;
void init(){
memset(ch,0,sizeof(ch));
memset(cnt,0,sizeof(cnt));
idx = 0;
memset(ne,0,sizeof(ne));
}
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]++;
}
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++;
}
}
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;
} 好了，今天的题目&答案到此为止qwq
标签：AC,ch,idx,Trie,++,cnt,int,自动机,scanf From： https://blog.csdn.net/jt6666678/article/details/139449160