前缀统计

题目

给定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;
}