首页 > 其他分享 >字典树模板

字典树模板

时间:2024-07-18 15:55:53浏览次数:9  
标签:end idx TrieNode tree son int 模板 字典

把数据都存在一个TrieNode数组里,只保存其指向关系。

class TrieNode {
public:
    bool end;
    vector<int> son;
    TrieNode() {
        end = false;
        son = vector<int>(26, -1);
    }
};

class Trie {
public:
    vector<TrieNode> tree;

    Trie() {
        tree.push_back(TrieNode());
    }

    bool query(string& s) {
        int idx = 0;
        for(char c : s) {
            int to = tree[idx].son[c - 'a'];
            if (to == -1) return false;
            idx = to;
        }
        return tree[idx].end;
    }

    void insert(string &s) {
        int idx = 0;
        for (char c : s) {
            if (tree[idx].son[c - 'a'] == -1) {
                tree[idx].son[c - 'a'] = tree.size();
                tree.push_back(TrieNode());
            }
            idx = tree[idx].son[c - 'a'];
        }
        tree[idx].end = true;
    }
};

标签:end,idx,TrieNode,tree,son,int,模板,字典
From: https://www.cnblogs.com/FlyingLight/p/18309699

相关文章

  • STL(标准模板库)理论基础
    STL标准模板库理论基础基本概念容器容器的分类迭代器算法迭代器C++标准库标准库中与语言支持功能相关的头文件支持流输入/输出的头文件与诊断功能相关的头文件定义工具函数的头文件支持字符串处理的头文件定义容器类的模板的头文件支持迭代器的头文件有关算法的头文件有......
  • [题解]P1452 【模板】旋转卡壳 | [USACO03FALL] Beauty Contest G
    P1452【模板】旋转卡壳|[USACO03FALL]BeautyContestG旋转卡壳模板题。凸包用的是Andrew算法,就不详述了,具体可以查查资料了解,但提一嘴Andrew算法的一些细节问题:Andrew算法的一些细节Andrew算法的模板代码如下:sort(a+1,a+1+n,cmp);st[++top]=1;for(inti=2;i<=n;i++){ ......
  • SpringBoot与Thymeleaf模板技术整合
    以下是一个简单的SpringBoot整合Thymeleaf的入门案例:1.创建一个SpringBoot项目,并添加Thymeleaf依赖。org.springframework.bootspring-boot-starter-thymeleaforg.springframework.bootspring-boot-starter-web2.在src/main/resources/templates目录下创建一个HTML模......
  • 易优CMS模板标签collect文档收藏
    [基础用法]标签:collect描述:文档收藏/取消标签用法:{eyou:collectid="collect"cancel="加入收藏"collect="已收藏"}<a{$collect.onclick}>{$collect.cancel}</a>收藏数:<span{$collect.numId}></span>次{$collect.hidden}{/eyou:c......
  • STM32寄存器操作、模板构建
    2024年7月18日发布于博客园,本文涉及到STM32F4XX和STM32F1XX系列目录外设寄存器查找①名称②偏移地址③寄存器位表④位功能说明寄存器基本操作C语言的置位和清零具体方法设置GPIO流程给寄存器赋值带参数宏STM32F1xx芯片识别存储器映射寄存器映射让GPIOB端口的16个引脚输......
  • 杭州外贸网站建设 最好用wordpress模板来搭建
    防护服wordpress外贸网站模板消防服、防尘服、隔热服、防化服、防静电服、电焊服wordpress外贸网站模板。https://www.jianzhanpress.com/?p=4116工业品wordpress外贸网站模板机械及行业设备、五金工具、安全防护、包装、钢铁、纺织皮革等工业品wordpress外贸网......
  • Python读Excel数据,创建Word文档上下文字典列表,元素为字典(新)
    #读Excel数据,创建Word文档上下文字典列表,元素为每个培训人员的上下文字典defcreate_docx_context_dict_list(_excel_path):"""输入参数::param_excel_path:Excel全路径功能:创建Word文档上下文字典列表,元素为每个培训人员的上下文字典字典的键为......
  • 2024-07-17 如何在vscode部署你的代码块,从而在新建页面时能快速搭建模板(windows环境)
    步骤一:打开vscode,按住ctrl+shif+p唤出命令窗口 步骤二:在窗口中输入命令,并回车Preferences:OpenUserSnippets 对,就是这个代码片段,接着输入你想添加代码的某某语言or脚本,比如我要添加vue的代码片段输入vue,回车,会显示vue.json文件出来给你更改,我的是这样 注意:如果你......
  • Goby漏洞发布 | CVE-2024-4879 ServiceNowUI /login.do Jelly模板注入漏洞【已复现】
    漏洞名称:ServiceNowUI/login.doJelly模板注入漏洞(CVE-2024-4879)EnglishName:ServiceNowUI/login.doInputValidationVulnerability(CVE-2024-4879)CVSScore:9.3漏洞描述:ServiceNow是一个业务转型平台。通过平台上的各个模块,ServiceNow可用于从人力资源和员工管理到自动......
  • 模板设计模式
    模板模式(TemplatePattern)是一种行为设计模式,它在一个方法中定义一个操作的骨架,而将一些步骤的实现延迟到子类中。模板方法模式使得子类可以在不改变算法结构的情况下,重新定义算法中的某些步骤。模板模式的组成部分抽象类(AbstractClass):定义算法的骨架,并包含一个模板方法。......