03-11 01:51 阅读 123

Trie字符串统计-acwing

记住一件事情即可：Trie是高效存储和查找字符串集合的数据结构

一般来说题目是会限制字母的种类，不会太多

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define rep(i,a,b) for(int i = a; i <= b ; i ++ )
#define pre(i,a,b) for(int i = b ; i >= a ; i --)
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define ios ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
typedef pair PII ;
const int N = 2e6 + 10;

int son[N][26],cnt[N],idx; //下标是0的点,既是根节点，也是空节点
char str[N];
int n;
void insert_string(char *str)
{
    int root=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-‘a‘;
        if(!son[root][u]) son[root][u]=++idx;
        root=son[root][u];
    }
    cnt[root]++;
}

int query(char *str)
{
    int root=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-‘a‘;
        if(!son[root][u]){
            return 0;
        }
        root=son[root][u];
    }
    return cnt[root];
}

int main()
{
    ios;
    cin>>n;
    while(n--)
    {
        char op[2];
        cin>>op>>str;
        if(op[0]==‘I‘)
        {
            insert_string(str);
        }
        else{
            cout<

原文：https://www.cnblogs.com/jxust-Biao/p/13338857.html

推荐资源

JavaEE 高并发高可用高性能架构设计VIP高级课程《抖音好物分享实操课》短视频带货秘诀，无需拍摄简单剪辑快速涨粉大数据开发工程师完整版 2021年获取最新项目的渠道方式，帮助我们快速打开新的认知和思维【视频课程】 101名师工厂商学院·短视频IP变现通关秘籍，大咖亲授带你避坑少走弯路老男孩徐培成_大数据课程大数据高薪就业视频(全套) 首次关于Golang高级爬虫实战课程+Golang语言实战应用之Beego轻博客开发教学价值400元网络编程实践视频教程 Google分布式系统专家数码单反从入门到精通高级摄影技巧教程 Python服务端工程师就业面试指导完整版