Category: 字符串

2024
算法字符串

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

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

算法字符串

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

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

算法字符串

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

摘要: 循环同构字符串中哪个字典序最小 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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 同构的概念前面我们提到的数据结构的同构的说法借鉴了近世代数中关于代数结构的同构的概念： 设有两个代数系统 $< A, \

算法字符串

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

摘要: 可以用字符串哈希解决的经典问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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 叉哈夫曼树和哈夫曼编码，并用于

算法字符串

字符串精确匹配

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

算法字符串

Trie

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