首页 > 其他分享 >Trie字符串统计题解

Trie字符串统计题解

时间:2024-01-08 10:37:20浏览次数:34  
标签:Trie 题解 ++ son char int str 字符串

维护一个字符串集合,支持两种操作:

  1. "I x"向集合中插入一个字符串x;
  2. "Q ×"询问一个字符串在集合中出现了多少次。

共有N个操作,输入的字符串总长度不超过105,字符串仅包含小写英文字母。

输入格式

第一行包含整数N,表示操作数。

接下来N行,每行包含一个操作指令,指令为"l ×"或"Q ×"中的一种。

输出格式

对于每个询问指令”Q x”,都要输出一个整数作为结果,表示x在集合中出现的次数。每个结果占一行。

数据范围

1 ≤ N ≤ 2 * 10^4

输入样例:

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

代码:

#include <iostream>
 
using namespace std;
 
const int N = 100010;
 
int son[N][26], cnt[N], idx; // 下标是0的点, 即是根节点,又是空节点
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;
}

标签:Trie,题解,++,son,char,int,str,字符串
From: https://blog.51cto.com/u_16492348/9139628

相关文章

  • java后台字符串URLencode、URLdecode及Base64加解密转换
    一、URLencode、URLdecode//将application/x-www-from-urlencoded字符串转换成普通字符串StringkeyWord=URLDecoder.decode("%E4%BD%A0%E5%A5%BD","utf-8");System.out.println(keyWord);//输出你好//将普通字符创转换成application/x-www......
  • python 使用多个界定符分割字符串
    问题你需要将一个字符串分割为多个字段,但是分隔符(还有周围的空格)并不是固定的。解决方案string对象的split()方法只适应于非常简单的字符串分割情形,它并不允许有多个分隔符或者是分隔符周围不确定的空格。当你需要更加灵活的切割字符串的时候,最好使用re.split()方法......
  • CF1536F Omkar and Akmar 题解
    思路首先最后的局面在两两字母间一定不会多于\(1\)个空格。考虑反证,假设有两个空格,那么有以下两种情况:\(\text{A}\_\_\text{B}\),\(\text{A}\_\_\text{A}\),也就是两边的字母不同,相同。对于第一种,在任意一个空格都可以填一个与他相邻字符不同的字符,对于第二种,填\(\text{B}\)......
  • CF1527D MEX Tree 题解
    思路如果一条路径的\(\text{mex}=k\),那么\(0\simk-1\)这些点一定在路径中出现过,并且一定在一条链上。如果不在一条链上,那么就不满足简单路径这一条件了。因此我们在从小到大加点的过程中如果发现一个点不在已求出的链上,那么比这个点编号大的\(k\)答案一定都是\(0\)了......
  • [ABC329E] Stamp 题解
    正难则反。直接往上覆盖不好做,那么可以考虑把字符从\(S\)上往下删。删的过程就是在\(S\)中找\(T\)并把他们变成#。如果\(S\)中有字符为#,那我们可以把它看成任意字符,因为向上贴的过程中有重复覆盖的情况,在删的时候我们并不知道他是否重复了,所以当成任意字符来看即可(这也......
  • [ABC331F] Palindrome Query 题解
    思路判断一个字符串是否是回文串,可以从它的本质出发:正着读和倒着读是一样的。快速判断它正着和反着是否一样,用字符串哈希即可。又因为涉及单点修改,区间查询,那么使用线段树维护这两个值就行了。这里讲一下如何pushup。以正着的哈希值为例:我们要更新\(p\)这个点的\(hash\)值,......
  • • python 脚本 输入字符串 输出字符串+当前时间 生成api http请求
    案例问题背景python脚本输入字符串输出字符串+当前时间生成apihttp请求脚本1这是单线程的单次处理单个http请求同时多个请求按照顺序处理而不是并行处理多请求!=多线程但是相关使用多线程来并行处理多请求使用flask或django等web服务器框架可以与wsgi服务器配合使用比如guni......
  • 字符串、字符“+”
    字符串“+”字符“+”字符串只有“+”操作......
  • 1 月杂题题解
    好久没写博客了?今晚写爽。P5311成都七中这有黑?对于一个点\(x\),设其子树任意一点为\(y\)。我们可以求出这\(x\rightarrowy\)这条路径经过节点的的\(l,r\)。遍历\(x\)的子树,我们可以得到一些三元组\((l,r,c)\)表示\(x\)所属连通块包含了\(l,r\)这些节点,就有一......
  • [ABC273D] LRUD Instructions 题解
    [ABC273D]LRUDInstructions题解很好的一道大模拟,使我爆\(0\)。思路解析大模拟,我们只需要用一个\(x,y\)表示我们当前的位置,而对于每一个移动,我们就判断在当前移动方向上离当前点最近的点,若该点在当前行进路线上,则把当前位置设为该点前面的一个。其中判断在当前移动方向上......