如何推广外贸网站,丁的老头seo博客,做票据业务的p2p网站,合肥住房城乡建设部的网站Trie字符串统计
维护一个字符串集合#xff0c;支持两种操作#xff1a; 1.I x向集合中插入一个字符串x 2.Q x询问一个字符串在集合中出现了多少次 共有N个操作#xff0c;输入的字符串总长度不超过 1 0 5 10^5 105#xff0c;字符串仅包含小写英…Trie字符串统计
维护一个字符串集合支持两种操作 1.I x向集合中插入一个字符串x 2.Q x询问一个字符串在集合中出现了多少次 共有N个操作输入的字符串总长度不超过 1 0 5 10^5 105字符串仅包含小写英文字母
输入格式
第一行包含整数N表示操作数 接下来N行每行包含一个操作指令指令为I x或Q x中的一种
输出格式
对于每个询问指令Q x都要输出一个整数作为结果表示x在集合中出现的次数 每个结果占一行
数据范围 1 ≤ N ≤ 2 ∗ 1 0 4 1\le N\le 2*10^4 1≤N≤2∗104
输入样例 5 I abc Q abc Q ab I ab Q ab 输出样例 1 0 1 AC代码
#includeiostream
using namespace std;const int N 1e5 10;// son[N][26] 存储Trie树中每个点的所有儿子
// cnt[N] 以当前点结尾的单词有多少个
// idx 存储当前用到的下标与单链表的idx同理
// 下标是0的点既是根结点又是空结点
int son[N][26], cnt[N], idx;
char str[N];void insert(char str[]) {int p 0;for(int i 0; str[i]; i) {int u str[i] - a;if(!son[p][u]) son[p][u] idx;p son[p][u];}cnt[p];
}int query(char str[]) {int p 0;for(int i 0; str[i]; i) {int u str[i] - a;if(!son[p][u]) return 0;p son[p][u];}return cnt[p];
}int main() {int n;scanf(%d, n);while(n--) {char op[2];scanf(%s%s, op, str);if(op[0] I) insert(str);else printf(%d\n, query(str));}return 0;
}
