企业官网建设流程全解析

紫金网站制作策划,wordpress 不同ip,seo顾问咨询,网站开发团队需要哪些信奥赛C提高组csp-s之Trie字典树详解 1. 什么是字典树#xff1f; 字典树#xff08;Trie#xff09;#xff0c;也称为前缀树#xff0c;是一种专门用于字符串检索的树形数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间#xff0c;是一种以空间换时间的数…信奥赛C提高组csp-s之Trie字典树详解1. 什么是字典树字典树Trie也称为前缀树是一种专门用于字符串检索的树形数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间是一种以空间换时间的数据结构。2. 字典树的构造过程2.1基本理论依据每个节点代表一个字符根节点不存储字符从根节点到任意节点的路径构成一个字符串前缀节点可以标记为终止节点表示从根到该节点的路径构成一个完整字符串2.2构造步骤以只包含小写字母的字符串集合为例假设我们要插入字符串集合[“abc”, “ab”, “bc”, “bcd”]步骤1初始化创建根节点编号0根节点有26个子节点指针对应a-z初始为空步骤2插入第一个字符串abc从根节点开始处理字符’a’检查根节点的’a’子节点不存在则创建新节点编号1移动到节点1处理字符’b’创建新节点编号2移动到节点2处理字符’c’创建新节点编号3在节点3标记为终止节点步骤3插入ab从根节点开始处理字符’a’a’子节点已存在节点1直接移动到节点1处理字符’b’b’子节点已存在节点2移动到节点2在节点2标记为终止节点新增标记步骤4继续插入其他字符串…3. 字典树的基本性质前缀共享具有相同前缀的字符串共享路径路径唯一性每个字符串对应从根节点到某个节点的唯一路径有序性如果按特定顺序遍历如字典序可以得到排序后的字符串集合多模式匹配适合同时查找多个字符串4. 时间复杂度与空间复杂度分析时间复杂度插入O(L)L为插入字符串的长度查询O(L)L为查询字符串的长度前缀查询O§P为前缀的长度空间复杂度最坏情况O(N×M×K)N字符串数量M平均字符串长度K字符集大小在实际应用中由于前缀共享空间通常小于最坏情况对于小写字母的静态数组实现O(节点数×26)5. 优缺点分析优点高效的字符串检索检索时间与字符串长度成正比与数据集大小无关前缀匹配方便适合实现自动补全、前缀搜索等功能字典序排序通过深度优先遍历可以按字典序输出所有字符串多模式匹配可以同时匹配多个模式串内存效率相对哈希对于大量有公共前缀的字符串比哈希表节省空间缺点空间消耗大每个节点需要存储字符集大小的指针数组字符集限制静态数组实现需要预先知道字符集大小内存碎片动态分配可能导致内存碎片不适合大规模字符集如Unicode字符集会消耗大量内存实现复杂度比哈希表实现复杂6. 在CSP信奥赛中的常见应用字符串检索快速判断字符串是否存在于集合中前缀统计统计具有某前缀的字符串数量最长公共前缀查找多个字符串的最长公共前缀异或问题01-Trie用于解决最大异或对等问题字典序问题按字典序处理字符串构造字典树的代码实现一、关键代码// 插入一个字符串到字典树voidinsert(chars[]){intp0;// 从根节点开始for(inti0;s[i]!\0;i){intxs[i]-a;// 将字符转换为0-25的数字if(trie[p][x]0){// 如果当前字符对应的分支不存在trie[p][x]idx;// 创建新节点}ptrie[p][x];// 移动到下一节点}cnt[p]1;// 标记当前节点为一个字符串的结尾}二、关键数组的含义和作用2.1trie数组2.1trie数组trie数组是**字典树前缀树**的核心数据结构int trie[N][26]; // 二维数组第一维trie[p]表示节点编号p第二维trie[p][x]表示从节点p出发通过字符x到达的下一个节点编号2.2cnt数组cnt数组状态标记数组cnt[p]用于标记节点p的状态三、构造结果图示假设我们要插入字符串集合[“abc”, “ab”, “bc”, “bcd”]详细构造过程分析一、初始状态trie数组全部初始化为 0表示没有边cnt数组全部初始化为 0表示没有节点被标记为单词结尾idx 0根节点编号为 0二、插入 “abc”第一个字符串1. 字符处理流程p 0 (根节点) 字符 a (x0): trie[0][0] 0 → 创建新节点: idx1, trie[0][0] 1 p 1 字符 b (x1): trie[1][1] 0 → 创建新节点: idx2, trie[1][1] 2 p 2 字符 c (x2): trie[2][2] 0 → 创建新节点: idx3, trie[2][2] 3 p 3 结尾: cnt[3] 12. 插入后的结构trie[0][0] 1 // 从根节点(0)经过a到节点1 trie[1][1] 2 // 从节点1经过b到节点2 trie[2][2] 3 // 从节点2经过c到节点3 cnt[3] 1 // 节点3标记为abc的结尾 树结构 0(根) └── a → 1 └── b → 2 └── c → 3 (结尾cnt1)三、插入 “ab”第二个字符串1. 字符处理流程p 0 字符 a (x0): trie[0][0] 1 ≠ 0 → p 1 (复用节点1) 字符 b (x1): trie[1][1] 2 ≠ 0 → p 2 (复用节点2) 结尾: cnt[2] 12. 插入后的结构trie[0][0] 1 // 保持不变 trie[1][1] 2 // 保持不变 trie[2][2] 3 // 保持不变 cnt[2] 1 // 节点2标记为ab的结尾 cnt[3] 1 // 节点3仍为abc的结尾 树结构 0(根) └── a → 1 └── b → 2 (结尾cnt1) └── c → 3 (结尾cnt1)注意节点2现在既是路径节点指向节点3又是单词ab的结尾节点。这是字典树的特性一个节点可以同时是多个单词的公共前缀节点和某个单词的结尾节点。四、插入 “bc”第三个字符串1. 字符处理流程p 0 字符 b (x1): trie[0][1] 0 → 创建新节点: idx4, trie[0][1] 4 p 4 字符 c (x2): trie[4][2] 0 → 创建新节点: idx5, trie[4][2] 5 p 5 结尾: cnt[5] 12. 插入后的结构trie[0][0] 1 // 从根节点经过a到节点1 trie[0][1] 4 // 从根节点经过b到节点4 (新增) trie[1][1] 2 // 从节点1经过b到节点2 trie[2][2] 3 // 从节点2经过c到节点3 trie[4][2] 5 // 从节点4经过c到节点5 (新增) cnt[2] 1 // 节点2为ab结尾 cnt[3] 1 // 节点3为abc结尾 cnt[5] 1 // 节点5为bc结尾 (新增) 树结构 0(根) ├── a → 1 │ └── b → 2 (结尾cnt1) │ └── c → 3 (结尾cnt1) └── b → 4 └── c → 5 (结尾cnt1)五、插入 “bcd”第四个字符串1. 字符处理流程p 0 字符 b (x1): trie[0][1] 4 ≠ 0 → p 4 (复用节点4) 字符 c (x2): trie[4][2] 5 ≠ 0 → p 5 (复用节点5) 字符 d (x3): trie[5][3] 0 → 创建新节点: idx6, trie[5][3] 6 p 6 结尾: cnt[6] 12. 插入后的最终结构trie[0][0] 1 // 从根节点经过a到节点1 trie[0][1] 4 // 从根节点经过b到节点4 trie[1][1] 2 // 从节点1经过b到节点2 trie[2][2] 3 // 从节点2经过c到节点3 trie[4][2] 5 // 从节点4经过c到节点5 trie[5][3] 6 // 从节点5经过d到节点6 (新增) cnt[2] 1 // 节点2为ab结尾 cnt[3] 1 // 节点3为abc结尾 cnt[5] 1 // 节点5为bc结尾 cnt[6] 1 // 节点6为bcd结尾 (新增) 树结构 0(根) ├── a → 1 │ └── b → 2 (结尾cnt1) │ └── c → 3 (结尾cnt1) └── b → 4 └── c → 5 (结尾cnt1) └── d → 6 (结尾cnt1)六、trie数组和cnt数组的最终状态表trie数组只显示非零值p\ca(0)b(1)c(2)d(3)说明01400根节点10200对应a20030对应ab30000对应abc40050对应b50006对应bc60000对应bcdcnt数组状态节点cnt值说明00根节点不是单词结尾10字符串a不是插入的单词21单词ab的结尾31单词abc的结尾40字符串b不是插入的单词51单词bc的结尾61单词bcd的结尾研究案例题目背景XS中学化学竞赛组教练是一个酷爱炉石的人。他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉。题目描述这之后校长任命你为特派探员每天记录他的点名。校长会提供化学竞赛学生的人数和名单而你需要告诉校长他有没有点错名。输入格式第一行一个整数n nn表示班上人数。接下来n nn行每行一个字符串表示其名字互不相同且只含小写字母长度不超过50 5050。第n 2 n2n2行一个整数m mm表示教练报的名字个数。接下来m mm行每行一个字符串表示教练报的名字只含小写字母且长度不超过50 5050。输出格式对于每个教练报的名字输出一行。如果该名字正确且是第一次出现输出OK如果该名字错误输出WRONG如果该名字正确但不是第一次出现输出REPEAT。输入样例5 a b c ad acd 3 a a e输出样例OK REPEAT WRONG说明/提示对于40 % 40\%40%的数据n ≤ 1000 n\le 1000n≤1000m ≤ 2000 m\le 2000m≤2000。对于70 % 70\%70%的数据n ≤ 10 4 n\le 10^4n≤104m ≤ 2 × 10 4 m\le 2\times 10^4m≤2×104。对于100 % 100\%100%的数据n ≤ 10 4 n\le 10^4n≤104m ≤ 10 5 m≤10^5m≤105。思路分析:这道题需要实现一个高效的字符串查询系统用于判断名字是否正确在名单中如果是正确的名字是否是第一次被点到数据结构选择使用字典树Trie存储所有学生名字因为名字只包含小写字母适合用26叉树查询时间复杂度为O(L)L是名字长度≤50非常高效空间复杂度相对合理状态标记设计用cnt[p]数组记录每个名字的状态0: 不是名字结尾 或 名字不存在1: 是名字结尾且未被点到过初始状态2: 是名字结尾且已被点到过代码实现:#includebits/stdc.husingnamespacestd;constintN5e510;// 最大节点数根据题目计算n≤10000每个名字长度≤50intn,m;// n: 学生人数m: 查询次数chars[60];// 临时存储名字的字符数组inttrie[N][26];// 字典树每个节点最多有26个子节点a-zintcnt[N];// 节点状态0-不存在/不是结尾1-是结尾未访问2-是结尾已访问intidx0;// 当前节点编号0是根节点// 插入一个名字到字典树voidinsert(chars[]){intp0;// 从根节点开始for(inti0;s[i]!\0;i){intxs[i]-a;// 将字符转换为0-25的数字if(trie[p][x]0){// 如果当前字符对应的分支不存在trie[p][x]idx;// 创建新节点}ptrie[p][x];// 移动到下一节点}cnt[p]1;// 标记当前节点为一个名字的结尾}// 查询名字的状态intquery(chars[]){intp0;for(inti0;s[i]!\0;i){intxs[i]-a;if(trie[p][x]0){// 如果路径中断名字不存在return0;// 返回0表示名字错误}ptrie[p][x];}// 根据结尾节点的状态返回相应值if(cnt[p]0){// 路径存在但不是名字结尾return0;// 名字错误}elseif(cnt[p]1){// 名字存在且是第一次点到cnt[p]2;// 更新状态为已访问return1;// 返回1表示OK}else{// 名字存在且已被点到过return2;// 返回2表示REPEAT}}intmain(){cinn;while(n--){scanf(%s,s);insert(s);// 插入所有学生名字}cinm;while(m--){scanf(%s,s);intresultquery(s);// 查询每个名字的状态if(result0){printf(WRONG\n);// 名字不存在}elseif(result1){printf(OK\n);// 名字正确且第一次点到}else{printf(REPEAT\n);// 名字正确但已点过}}return0;}功能分析:1.数据结构功能字典树高效存储和检索字符串状态数组记录每个名字的访问状态2.算法流程建树阶段将所有学生名字插入字典树查询阶段对每个查询的名字在字典树中按字符查找如果中途路径中断 → 名字错误WRONG如果找到完整名字状态为1 → 第一次点到OK更新状态为2状态为2 → 重复点到REPEAT3.时间复杂度插入O(L) 每个名字总 O(n*L)查询O(L) 每个名字总 O(m*L)其中 L ≤ 50可以高效处理大规模数据4.空间复杂度最坏情况每个节点都有26个子节点实际空间N 5e510足够容纳所有名字5.关键设计点用状态数组避免重复查询时的重复计算字典树避免了字符串比较查询速度极快使用静态数组而非动态分配提高访问效率6.边界情况处理名字长度≤50字符数组大小设为60名字只包含小写字母简化了字典树设计名字互不相同简化了状态管理样例演示:输入5a b c ad acd3a a e 字典树构建 root/|\ a b c|\ d c|d 查询1.a→ 找到状态1→ OK状态变为22.a→ 找到状态2→ REPEAT3.e→ 找不到 → WRONG更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、csp高频考点知识详解及案例实践CSP信奥赛C之动态规划CSP信奥赛C之标准模板库STL信奥赛C提高组csp-s知识详解及案例实践四、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}