Tag: 字符串

中心扩散法

摘要: 枚举中点,看两边能扩散多长 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文通过最长回文子串问题,看一下数组上关于子数组的问题的两种不同方向的思考方式,一种是首先确定子数组的两端 l, r

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

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

Trie单串多模式匹配

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

字典序法枚举排列

摘要: 按照字典序来枚举全排列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 回溯法的思想、设计与分析 中,我们系统学习了回溯法。回溯法将解空间看做树形结构,称为状态空间树,在文章 回溯法三

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

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

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

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

参考字符串哈希定义数组哈希(数组的同构)

摘要: 类似于字符串哈希的数组哈希,以及在数组同构中的应用。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中我们学习了字符串哈希的原理与代码模板。 对于长度为 m 的字符串 s

力扣940-不同的子序列

摘要: 不同的子序列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个比较难的问题,算法的核心是动态规划,根据动态规划阶段的不同选取方式,有普通的一维线性DP,以及序列自动机两种做法。

序列自动机

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

深入Java字符串

摘要: 本文是关于 Java 中的字符串的要点总结。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings == 与 equals12345String str1 = String("abc");Stri

字符串哈希的哈希函数

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

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

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

小数转分数

摘要: 小数转分数的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一下在数学算法中常见的小数转分数的问题。在编程中,除了整数以外,我们主要用的是小数,比如 float、double

字符串哈希

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

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

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

【设计难题】力扣642-设计搜索自动补全系统

摘要: 自动补全系统设计,基于 Trie 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 题目 642. 设计搜索自动补全系统 为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句(最少

双向Trie

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

【多维分桶】力扣527-单词缩写

摘要: 桶外分类、桶内排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个分桶的问题。首先根据需求对字符串设计一种哈希值,该值包含了词的长度信息,首字符和尾字符信息。然后依据

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

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

在模拟过程中找出循环节

摘要: 循环节优化模拟;倍增优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在模拟的过程中,如果出现了循环节,就可以直接跳过很多中间的模拟步骤。有时这种循环节是现成已知的,例如文章 通过已知

子序列匹配

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

【STL】字典序比较 lexicographical_compare

摘要: 本文介绍在 C++ STL 中的字典序比较方法 lexicographical_compare 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍在 C++ STL 中的字典序比较方法

【C++17】string_view

摘要: 本文介绍 C++17 中的一个字符串相关的新特性 string_view,主要参考《C++17 STL Cookbook》$7-3 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍 C

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 叉哈夫曼树和哈夫曼编码,并用于

Redis中字符串的编码

摘要: Redis 中字符串的编码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings Redis字符串类型内部编码 src/server.h src/sds.h src/object.c 相关题目

稀疏相似度:倒排索引

摘要: 倒排索引简介及其在稀疏相似度中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 单词-文档矩阵单词—文档矩阵是表达两者之间所具有的一种包含关系的概念模型,每列代表一个文档,每行代表一个单

Trie

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