Tag: 字符串

2023
算法字符串

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

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

算法字符串

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

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

算法数据结构

参考字符串哈希定义数组哈希（数组的同构）

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

算法leetcode

力扣940-不同的子序列

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

算法字符串

序列自动机

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

2022
编程Java

深入Java字符串

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

算法字符串

字符串哈希的哈希函数

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

算法动态规划

双串线性DP,二维状态表示阶段

子序列匹配 392. 判断子序列 115. 不同的子序列 字符串模糊匹配 72. 编辑距离 712. 两个字符串的最小ASCII删除和 583. 两个字符串的删除操作 44. 通配符匹配 10. 正则表达式匹配 其它 97. 交错字符串 727. 最小窗口子序列 1458. 两个子序列的最大点积 $0 双串线性 DPdp[i][j]: i

算法leetcode

力扣1316-不同的循环子字符串

字符串哈希 前缀哈希 string_view kmp $1 题目题目链接 1316. 不同的循环子字符串 题目描述给你一个字符串 text ，请你返回满足下述条件的 不同 非空子字符串的数目： 可以写成某个字符串与其自身相连接的形式（即，可以写为 a + a，其中 a 是某个字符串）。例如，abcabc 就是 abc 和它自身连接形成的。 提示：121 <= text.len

算法字符串

字符串哈希

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

算法leetcode

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

Trie $1 题目题目链接 642. 设计搜索自动补全系统 题目描述为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句（最少包含一个字母，以特殊字符 ‘#’ 结尾）。除 ‘#’ 以外用户输入的每个字符，返回历史中热度前三并以当前输入部分为前缀的句子。下面是详细规则： 一条句子的热度定义为历史上用户输入这个句子的总次数。返回前三的句子需要按照热度从高到低排序（第一个是最热门的）。如果有

算法字符串

双向Trie

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

算法leetcode

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

用哈希的方式对多属性分桶 维护桶内元素 排序 Trie $1 题目题目链接527. 单词缩写 题目描述给定一个由n个不重复非空字符串组成的数组，你需要按照以下规则为每个单词生成最小的缩写。 初始缩写由起始字母+省略字母的数量+结尾字母组成。若存在冲突，亦即多于一个单词有同样的缩写，则使用更长的前缀代替首字母，直到从单词到缩写的映射唯一。换而言之，最终的缩写必须只能映射到一个单词。若缩写并不

算法字符串

后缀数组

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

算法leetcode

【DP难题】力扣466-统计重复个数

循环节优化暴力模拟 倍增优化DP 序列自动机 $1 题目题目链接466. 统计重复个数 题目描述由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，[“abc”,3]=“abcabcabc”。 如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，”abc” 可以从 “abdbec” 获得，但不能从 “acb

算法字符串

子序列匹配

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

编程C++

【STL】字典序比较 lexicographical_compare

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

编程C++

【C++17】string_view

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

算法leetcode

单词矩阵

【搜索难题】力扣425-单词方块 数据结构维护状态转移时所需的查询需求 剪枝手段: 剪枝 $1 题目题目链接面试题 17.25. 单词矩阵 题目描述给定一份单词的清单，设计一个算法，创建由字母组成的面积最大的矩形，其中每一行组成一个单词(自左向右)，每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现，但要求所有行等长，所有列等高。 如果有多个面积最大的矩形，输出任意一个均可。一

算法字符串

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 这两种值

算法leetcode

【搜索难题】力扣425-单词方块

DFS 数据结构维护状态转移 $1 题目题目链接425. 单词方块 题目描述给定一个单词集合 （没有重复），找出其中所有的 单词方块 。 一个单词序列形成了一个有效的单词方块的意思是指从第 k 行和第 k 列 (0 ≤ k < max(行数, 列数)) 来看都是相同的字符串。 例如，单词序列 [“ball”,”area”,”lead”,”lady”] 形成了一个单词方块，因为每个单词从水

算法字符串

字典序

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

AI工程数据库系统

Redis中字符串的编码

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

算法字符串

字符串精确匹配

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

算法字符串

Trie

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