Category: 字符串

2024
算法字符串

字符串精确匹配的主流算法总结（含书籍推荐）

摘要: 字符串精确匹配方法汇总 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，此前我们讨论了字符串精确匹配的很多主流算法。 实际上字符串匹配算法是一个单独的大课题，这里推荐一本书 《Algo

算法字符串

暴力算法更实用：字符串匹配平均比较次数

摘要: 字符串匹配的暴力算法平均情况时间复杂度 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 KMP算法与代码模板 中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它

算法字符串

字符串精确匹配 | BM算法的变种-Horspool算法

摘要: BM算法的变种，Horspool算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字符串精确匹配的BM算法 中，我们介绍了字符串精确匹配的 BM 算法。在实际应用的经验中，BM 算

算法字符串

字符串精确匹配BM算法的变种：Sunday算法

摘要: BM算法的变种，Sunday算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在上一篇文章 字符串精确匹配的BM算法 中，我们介绍了字符串精确匹配的 BM 算法。在实际应用的经验中，BM

算法字符串

处理重复叠加串上的匹配问题：滚动哈希法

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

算法字符串

多次查询两个子串是否相等：前缀哈希法

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

算法字符串

字符串精确匹配的BM算法

摘要: BM算法原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 KMP算法与代码模板 中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它是一种预处理+响

算法字符串

字符串的循环同构与最小表示法

摘要: 循环同构字符串中哪个字典序最小 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 问题背景给定一个字符串 s，如果不断把最后一个字符放在开头，最终会得到 $n$ 个字符串，称这 $n$ 个字符串

2023
算法字符串

Manacher算法：基于对称性的优化，信息论直觉

摘要: 最长回文子串的 Manacher 算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个解决最长回文子串的专门算法：Manacher 算法。Glenn K. Manacher在1

算法字符串

设计内存文件系统：在Trie中用TreeMap维护子节点

摘要: TreeMap 维护子节点的 Trie 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 Trie 中，一般用数组或哈希表维护子节点，本文我们看一个用TreeMap维护子节点的例子。 题

算法字符串

Trie单串多模式匹配

摘要: 单纯多模式匹配 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文看一个 Trie 可以完美解决的字符串匹配需求，单串多模式匹配，且模式中的字符没有限制，也就是单串中的每个字符都有可能是

算法字符串

字符串同构问题：最小表示法与哈希表

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

算法字符串

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

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

算法字符串

KMP算法与代码模板

摘要: KMP算法原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字符串精确匹配 中，我们汇总了字符串精确匹配的各种算法，其中 KMP 算法是比较难但是思想比较重要的一种， 本

算法字符串

序列自动机

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

2022
算法字符串

字符串哈希的哈希函数

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

2020
算法字符串

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

摘要: 一类字符串匹配需求。在单个串中匹配多个模式串 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 背景给定单串 s，n 个模式串 p1, p2, ..., pn。 其中 n 个模式串中，任意两个模

算法字符串

字符串哈希

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

算法字符串

高度数组：后缀数组中相邻两个后缀的最长公共前缀

摘要: 高度数组 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings $0 背景高度数组是后缀数组中相邻两个后缀的最长公共前缀(LCP)。 1lcp[i] := s[sa[i]..n-1] 与

算法字符串

双向Trie

摘要: 在一个 Trie 节点同事维护前缀和后缀 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings $0 双向Trie场景一个 Trie 可以预处理一批单词的所有前缀，或者所有后缀。此后可以快速进行与前

算法字符串

后缀数组：排名为i的后缀的起始下标

摘要: 后缀数组原理与实现 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 背景一个长度为 n 的字符串 s，共有 n 种后缀。现在想对这 n 个后缀排序，将排序结果保存在一个数组 sa 中。sa[i

算法字符串

子序列匹配

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

算法字符串

Trie题目汇总

摘要: Trie 的题目总结 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings Trie 基本功能的思想和实现参考文章：Trie 题目 备注 208. 实现 Trie (前缀树)

算法字符串

01Trie

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

算法字符串

用字典树处理字典序的问题

摘要: 几个字符串上的字典序问题，用字典树可以解决 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字典序法枚举排列 中，我们了解到对于一个排列来说，可以用字典序来定义这些排列的大小，进一步可

算法字符串

比较简单的两种字符串的编码与解码

摘要: 字符串的编码解码，分隔符、分块编码 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 哈夫曼树与哈夫曼编码 和 k叉哈夫曼树 中，我们学习了 2 叉和 k 叉哈夫曼树和哈夫曼编码，并用于

算法字符串

Trie

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