Category: 字符串

字符串哈希-字符串同构问题

摘要: 字符串同构问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 数据结构的同构问题是哈希表解决的一个基本问题,在给定数据结构的同构规则后,如何快速判断两个数据结构是否同构。 对于这种判定同构的

用字符串哈希解决经典问题:最长重复子串、最长公共子串

摘要: 可以用字符串哈希解决的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中,我们学习了字符串哈希的原理和代码模板。 一些字符串中的经典问题用字符串哈希都可以解决,比

序列自动机

摘要: 序列自动机原理、代码模板、应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们串讲一下序列自动机的原理和代码模板。然后解决力扣 392。 序列自动机在文章 词法分析-有限自动机 中,

字符串哈希的哈希函数

摘要: 字符串哈希的哈希函数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中,我们探讨了字符串哈希,及其在字符串相关的经典问题中的应用。 字符串哈希是哈希中最常见的形式,在搜索

Trie单串多模式匹配,模式开头为统一特殊字符

$0 背景给定单串 s,n个模式串 p1, p2, …, pn。 其中 n 个模式串中,任意两个模式串都没有子串的关系,且都以一个特殊字符开头,模式的其它字符不会出现该特殊字符。 在 s 中找到所有匹配到这 n 个模式串的所有起始位置。 Trie用 n 个模式串建立一个 Trie。推进 i 的字符时,如果 s[i] 为特殊字符,则记录 j = i,并初始化 iter = root,之后尝试同时推进

字符串哈希

摘要: 本文系统梳理了字符串哈希相关的要点,并通过字符串精确匹配问题给出代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们系统串讲一下字符串哈希算法。字符串哈希是一种哈希函数

双向Trie

Trie基础 trie 01Trie 双向Trie 场景及方案 实现 745. 前缀和后缀搜索 算法1:双向 Trie 算法2:前缀Trie + 后缀Trie $0 双向Trie场景一个 Trie 可以预处理一批单词的所有前缀,或者所有后缀。此后可以快速进行与前缀匹配或者后缀匹配有关的查询。 有时需求会更近一步:即做一些前缀和后缀均需要匹配的查询。例如问前缀为 profix 同时

后缀数组

倍增法 基数排序: 非比较排序 后缀数组 1163. 按字典序排在最后的子串 基于后缀数组的字符串匹配 预处理 sa + 二分排名(sa的下标) 高度数组 $0 背景一个长度为 n 的字符串 s,共有 n 种后缀。现在想对这 n 个后缀排序,将排序结果保存在一个数组 sa 中。sa[i] := 排名为 i 的后缀的起始下标。 1234sa[i] := 排名为 i 的后缀的起

子序列匹配

摘要: 子序列匹配问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串精确匹配 中我们学习了字符串精确匹配的问题,本文我们看一下子序列匹配问题,涉及到贪心、动态规划、序列自动机等算法。

Trie题目汇总

Trie 基本功能的思想和实现 : 力扣208-Trie 208. 实现 Trie (前缀树) Trie 的插入,查找单词和前缀是否存在 211. 添加与搜索单词 - 数据结构设计 Trie 中的搜索 基于字典树的串上搜索 212. 单词搜索 II Trie + DFS 720. 词典中最长的单词 Trie + DFS 425. 单词方块 Trie + DFS 745. 前缀和后缀搜索

01Trie

摘要: 01Trie 的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 Trie 中我们了解了 Trie 的原理与实现。如果 Trie 的节点只含有 0, 1 这两种值

字典序

386. 字典序排数 440. 字典序的第K小数字 1643. 第 K 条最小指令 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串 $1 386. 字典序排数算法1: 字典树前序遍历字符集是 0123456789,将所有数字插入到字典树 按字典序输出所有数字,即对字典树前序遍历,将所有插入的数字输出,实现时与 N 叉树的前序遍历没有区别 123456789101112131

字符串精确匹配

摘要: 字符串精确匹配方法汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以 leetcode 第 28 题为模板题,总结一下字符串精确匹配的各种算法。 字符串精确匹配主流算法 暴力算

Trie

摘要: 经典的 Trie 的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以力扣 208 作为模板题来学习一下 Trie 的建树,插入和查找。并形成代码模板。 模板题