前缀统计
题目
给定N个字符串S1,S2,…,SN,接下来进行M次询问，每次询问给定一个字符串T，求S1~Sn中有多少个字符串是T的前缀。并且全部由小写字母组成
输入
第一行：一个字符串T（长度小于1000）
第二行：n(<=20000)
接下来n行，每行一个字符串（长度小于T的长度）
输出
一个整数，表示有多少个字符串是T的前缀
样例
样例输入1
abcdefg
3
abc
abd
a
样例输出1
2
思路
题目意思已经相当清楚，就是求在给定字符串中有多少个是T的前缀。
看到这里不妨先自己想一下在接着看
首先，我们看出是用字典树实现的（不清楚的朋友看这里）,而且是一道基础题
然后我们上代码
#include<bits/stdc++.h>
using namespace std;
int n;
char t[1005];
int zds[100005][26];//注意大小，稍不注意就会爆炸
int cnt[100005];
int num = 0;
void insert(char w[]) {//插入
int p = 0;
for(int i = 0; w[i]; i ++) {
int c = w[i]-'a';
if(!zds[p][c]) zds[p][c] = ++ num;
p = zds[p][c];
}
cnt[p] ++;
}
int query(char w[]) {//询问是否是t的前缀
int p = 0;
for(int i = 0; w[i]; i ++) {
int c = w[i]-'a';
if(!zds[p][c]) return 0;
p = zds[p][c];
}
return 1;
}
int main() {
cin >> t >> n;
insert(t);//将t加入字典树
int ans = 0;
for(int i = 1; i <= n; i ++) {
char a[1005];
cin >> a;
if(query(a)) ans ++;//询问如果是那么ans++
}
cout << ans;
return 0;
}