Category: 字符串

2023
算法字符串

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

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

算法字符串

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

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

算法字符串

序列自动机

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

2022
算法字符串

字符串哈希的哈希函数

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

2020
算法字符串

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 的建树，插入和查找。并形成代码模板。 模板题