教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载字符串是计算机科学中最基础也最常用的数据类型之一几乎所有系统搜索引擎、编译器、文本编辑器、网络协议、数据库都离不开对字符串的高效处理。本指南以 Learn-Algorithms 仓库的 字符串算法总览 为骨架系统讲解字符串的排序、查找单词查找树与子串查找、正则表达式、数据压缩四大核心算法方向并结合仓库内的 Trie 实现、赫夫曼编码笔记、KMP 算法笔记与面试代码逐层深化。读完本文你将掌握字符串子串问题的滑动窗口通用框架、Trie 前缀树的插入查询实现、KMP/BM 匹配思路以及基于频率统计的赫夫曼压缩流程并能直接迁移到自己的项目中。字符串算法全景四大方向在计算机中字符串的处理需求可以归结为四个经典方向这也是 Learn-Algorithms 仓库1 String/README.md给出的核心脉络排序Sorting对大量字符串按字典序等规则排序经典比较排序算法快排、归并、堆排序等均可直接应用详见仓库的 排序算法笔记查找Searching包括单词查找树Trie——利用公共前缀加速多字符串的检索、排序与统计以及子串查找——在一段文本中定位某个模式串的出现位置正则表达式Regular Expression模式匹配的基础是一般化了的子字符串查找问题也是搜索工具grep的核心数据压缩Data Compression利用统计特性压缩字符串存储空间经典方法包括赫夫曼树Huffman Tree与游程编码Run-Length Encoding, RLE。仓库中给出了 Java 中 String 实现的参考入口Java 中 String 实现适合在讨论具体语言层面的字符串不可变性、字符数组存储时对照阅读。此外仓库 README 总览 将字符串算法列为基本数据结构与算法的重要一环并指明子串查找的进阶题库参考字符串常见题目。查找一子串查找——从 KMP 到 BM子串查找是字符串算法中应用最广、研究最深入的问题给定文本串与模式串找出模式串在文本中第一次出现或全部出现的位置。KMP 算法线性时间匹配KMP 全称Knuth–Morris–Pratt算法1977 年由 Donald KnuthK、James H. MorrisM、Vaughan PrattP共同提出。它的核心价值在于可以在 O(nm) 的时间复杂度内完成两个字符串的匹配n 为文本长度m 为模式串长度详见仓库笔记 KMP.md。朴素匹配算法在失配时只能将模式串右移一位重新比较最坏复杂度为 O(n×m)。KMP 的关键改进是当某个位置失配时利用已匹配前缀的信息通过预先计算的 next/前缀函数数组跳过不可能匹配的位置避免文本指针回溯。匹配过程整体呈现线性复杂度因此 KMP 是众多文本处理工具、编辑器查找功能与 DNA 序列匹配场景的基石算法。仓库 README 总览 也将 KMP 列为15 个经典基础算法之一并链接到 KMP 字符串匹配算法可见其在算法体系中的基础地位。BM 算法从右向左的跳跃式匹配除 KMP 外仓库还收录了BMBoyer–Moore算法。BM 的思想与 KMP 相反从模式串的右端向左比较并在失配时依据坏字符规则Bad Character Rule与好后缀规则Good Suffix Rule让模式串尽量大幅右移从而跳过大量无需比较的字符。在自然语言文本等模式下BM 的平均效率常优于 KMP因此许多经典文本搜索工具如 grep 的早期实现都采用 BM 或其变体。两者互为补充KMP 保证最坏情况线性BM 平均性能突出。查找二单词查找树Trie / 前缀树当需要同时维护并检索大量字符串时逐条二分或顺序比较效率有限。Trie字典树 / 单词查找树利用字符串之间的公共前缀把一组关键字组织成一棵多叉树。仓库 字典树 Trie 笔记 给出了完整的定义与实现细节。Trie 的结构定义Trie 的三个基本性质除根节点外每个节点包含一个字符从根节点到某一节点路径上经过的字符连接起来即为该节点对应的字符串每个节点的所有子节点包含的字符互不相同保证每个节点对应的字符串唯一。例如下面这棵 Trie 可以表示字符串集合{a, to, tea, ted, ten, i, in, inn}/ \ / | \ t a i / \ \ o e n /|\ / a d n n关键认知是Trie 把每个关键字保存在一条路径上而不是一个节点中两个有公共前缀的关键字会共享前缀部分的路径——这正是前缀树Prefix Tree名称的由来。优缺点与应用场景优点插入与查询都是 O(m)m 为字符串长度与字典大小无关可对关键字按字典序排序借助公共前缀最大限度减少无谓比较。缺点比较费内存处理大数据时内存吃紧当散列函数设计良好时哈希表查询效率可能更优。典型应用包括前缀查询、字符串查询与排序、文本词频统计搜索引擎、索引结构、敏感词过滤垃圾评论系统。仓库源码trie.c 的插入与查询仓库提供了可运行的 C 实现 trie.c其节点结构如下#define ALPHABET_SIZE 26 // 256 typedef struct node { int count; //count 如果为0则代表非黄色点count0代表是黄色点同时表示出现次数; char value; //字符 struct node * subtries[ALPHABET_SIZE]; //子树 } Trie;插入从根出发逐个字符检查对应分支*p - a映射到 26 个槽位分支不存在则新建节点int trie_insert(Trie *trie, char *c){ char *p c; Trie *temp trie; while(*p ! \0){ if (temp-subtries[*p-a]NULL) { struct node *newNode (struct node *)malloc(sizeof(struct node)); newNode-value *p; temp-subtries[*p-a] newNode; } temp temp-subtries[*p-a]; p; } return 0; }查询沿路径逐字符匹配直到串尾全部匹配则返回 YESbool trie_query(Trie *trie, char *c){ char *p c; Trie *temp trie; while (*p!\0) { if (temp-subtries[*p-a]!NULL temp-subtries[*p-a]-value*p) { temp temp-subtries[*p-a]; p; continue; } break; } if (*p \0) return YES; return NO; }该文件自带的main函数演示了完整流程先向 Trie 中插入{int,integer,float,char,nonstriater,weibo}六个单词再依次查询cha应返回 NO、char应返回 YES、hello应返回 NO。注意trie.c中count字段注释表明它可同时用于词频统计count0 表示该节点是完整单词的结尾并记录出现次数。Trie 的存储取舍与工程变体从源码结构看subtries[ALPHABET_SIZE]的定长数组实现简单直接但存在明显权衡详见 Trie 笔记数组存储查询快但若系统中存在大量字符串且它们基本没有公共前缀将消耗大量内存链表存储省内存但查询时需要遍历链表效率下降。实际工程中常使用**双数组 TrieDouble-Array Trie, DATrie**等压缩变体来减少内存占用海量数据处理场景也常将 Trie 与哈希、Bloom Filter 组合使用可参考仓库 海量数据处理 的 Trie 一节。正则表达式与 grep模式匹配的通用语言正则表达式是模式匹配的基础它把子串查找一般化不仅匹配固定字符串还能匹配满足某种**模式pattern**的文本。例如^[a-z][a-z]\.com$可以匹配特定格式的邮箱地址。其核心价值在于用简洁的符号系统描述字符集合、重复次数、位置锚点与分组捕获是搜索工具grep、编辑器查找替换、词法分析器、日志分析系统的共同底座。grep 之所以强大正是因为它把正则表达式编译为自动机DFA/NFA并在文本流中高效执行匹配。理解子串查找KMP/BM 解决固定串与正则匹配解决模式串的关系是进阶文本处理的关键一步。数据压缩赫夫曼编码与游程编码数据压缩利用文本的统计特性如字符频率分布、连续重复降低存储空间。仓库字符串总览给出了两条经典路线赫夫曼树与游程编码。赫夫曼编码按频率分配编码长度仓库 赫夫曼编码笔记 给出了完整流程。赫夫曼编码由 Huffman 于 1952 年基于香农1948与 Fano1949的编码思想提出是一种不定长编码核心原则是出现频率越高的字符编码越短频率越低的字符编码越长从而整体上缩短编码总长。节点结构struct node{ char *huffCode; // 叶子节点的huff编码 int weight; // 出现频率权重 struct node *left, *right; }压缩四步统计扫描输入文件统计各字符出现次数可用哈希表并按频率排序建树采用贪心策略每次选取频率最低的两个节点合并成一个新节点其权重为两者之和需要**优先队列priority queue / 最小堆**辅助反复合并直至只剩一棵二叉树编码遍历赫夫曼树左分支记为 0、右分支记为 1得到每个字符的编码存入哈希表编码表重编码再次扫描文件按编码表逐字符替换输出压缩数据。之所以赫夫曼编码是前缀无关的所有字符都位于叶子节点因此不存在某个编码是另一个编码的前缀的情况解码无需分隔符即可唯一还原。为保证可解压压缩文件需附带文件头以重建赫夫曼树通常包括被编码的文本长度unsigned int size字符频率表unsigned char freqs[NUM_CHARS]解压则是对称的读取文件头 → 重建赫夫曼树 → 逐 bit 遍历编码流从根出发遇 0 进左子树、遇 1 进右子树直到叶节点输出对应字符。游程编码RLE压缩连续重复字符游程编码Run-Length Encoding是另一种更朴素的压缩思路对连续出现的相同字符记录字符 连续次数。例如aaabcc可压缩为a3bc2。仓库面试代码 string.c 中给出了compress()的就地压缩实现思路并特别提醒一个工程细节连续字符数量大于 9 时需要处理多位数计数否则会丢失信息。RLE 在文本存在大量连续重复如空格填充、缩进代码、BMP/简单图像时效果显著且实现成本远低于赫夫曼编码。滑动窗口解决字符串子串问题的通用框架字符串的许多高频问题最长无重复子串、最小覆盖子串、字符串排列、满足条件的最短/最长窗口都可以统一用**滑动窗口Sliding Window**解决。1 String/README.md给出了这套代码框架int left 0, right 0; while (right s.size()) { // 增大窗口 window.add(s[right]); right; while (window needs shrink) { // 缩小窗口 window.remove(s[left]); left; } }核心思路是维护left, right)这样一个窗口扩大右边界right不断右移把新字符加入窗口同时更新窗口内数据收缩左边界当窗口不再满足约束条件时left右移并移出左侧字符直到重新满足条件记录答案在合适的时机通常是收缩前后用当前窗口长度更新最优结果。窗口内的数据通常用哈希表unordered_mapchar, int或计数数组维护以便 O(1) 判断某个字符的出现次数是否超标。实战最长无重复子串仓库面试题笔记 [字符串-查找 给出了最长无重复子串如abcabbcbb输出 3的滑动窗口实现正是上述框架的直接应用int lengthOfLongestSubstring(string s) { unordered_mapchar, int window; int left 0, right 0; int res 0; // 记录结果 while (right s.size()) { char c s[right]; right; // 进行窗口内数据的一系列更新 window[c]; // 判断左侧窗口是否要收缩 while (window[c] 1) { char d s[left]; left; // 进行窗口内数据的一系列更新 window[d]--; } // 在这里更新答案 res max(res, right - left); } return res; }当某个字符在窗口内出现次数超过 1 时收缩左边界保证窗口始终无重复再以right - left更新答案。实战最小覆盖子串Hard同一笔记还收录了滑动窗口的进阶题目最小覆盖子串给定字符串 s 与 t在 s 中找出包含 t 所有字母的最小子串。例如s ADOBECODEBANC、t ABC时输出BANC。这类问题的通用模板是用两个哈希表分别记录 t 的需求与窗口内的命中情况右指针扩张窗口直至完全覆盖 t在保持覆盖的前提下收缩左指针不断比较并更新最小窗口重复直至右指针到达串尾。同一篇笔记还整理了滑动窗口思想的旁支两个指针双指针方案、最长回文子串的中心扩展法palindrome(s, i, i)与palindrome(s, i, i1)分别处理奇数/偶数长度回文等可作为滑动窗口体系的延伸练习。字符串排序与相关面试实战字符串排序可直接复用经典比较排序快排、归并、堆排序等仓库 排序算法笔记 系统收录了冒泡、选择、插入、希尔、快排、归并、堆排序与桶排序并特别点出两条与字符串算法相关的洞察归并排序是二叉树的后序遍历思路快排是二叉树的前序遍历思路理解这一点有助于把排序递归结构迁移到其他分治算法当数据如全校学生分数存在明显范围特征时可以用桶排序以 O(n) 完成——这与字符串按字典序排序时先按首字符分桶、再递归排序的思路一脉相承。此外仓库面试代码目录 codes/1 string 提供了丰富的字符串实操练习可与本文主题对照巩固char_first_appear_once.c找出第一个只出现一次的字符——两次扫描 长度 256 的哈希表hash[*tmp]第一次统计频率、第二次找第一个频率为 1 的字符。笔记 字符串-查找 特别提醒char 的范围是 -128~127unsigned char 才是 0~255直接用 char 作哈希索引需格外小心revert_by_word.c按单词逆序how are you ? → 单词反转再整句反转体现先局部逆序再整体逆序的两步技巧proc.c双指针在字符串内部交换大小写字符展示了指针技巧在原地修改场景的应用string.c集中了字符串反转、回文判断、首字符统计、过滤数字、删除指定字符、游程压缩等多个小函数的骨架注释中还记录了诸如连续字符个数超过 9 需处理多位数的实战经验。这些练习与本文的 Trie、KMP、滑动窗口相互印证哈希表解决统计类问题指针技巧解决原地修改类问题滑动窗口解决区间类问题前缀树解决多串检索类问题。小结与学习路径建议字符串算法的学习可以沿如下路径推进打牢基础掌握字符串的存储与指针/下标操作参考 Java 中 String 实现 理解语言层面的不可变与字符数组掌握子串查找朴素 BF → KMP线性最坏复杂度→ BM平均性能更优参考 KMP.md掌握多串数据结构实现一遍 trie.c理解公共前缀带来的检索、排序与词频统计能力掌握区间问题套路把 滑动窗口框架 练熟并用最长无重复子串最小覆盖子串验证见 字符串-查找理解压缩与模式匹配对照 赫夫曼编码笔记 走一遍统计→建树→编码→解码闭环理解正则表达式作为 grep 内核的角色。字符串算法在搜索引擎倒排索引、词频统计、网络协议报文解析、数据库索引键比较、安全敏感词过滤等场景无处不在本文覆盖的四大方向加上滑动窗口与 Trie 源码足以构成一套可实战、可面试、可迁移到工程中的完整字符串算法工具箱。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐终极指南如何用霍夫曼编码实现高效字符串压缩——Learn-Algorithms项目实战终极指南如何用霍夫曼编码实现高效字符串压缩——Learn Algorithms项目实战 霍夫曼编码是一种经典的字符串压缩算法通过字符出现频率构建最优二叉树教程Learn-Algorithms 面试字符串专题回文、atoi、滑动窗口与双指针等高频算法题全解Learn Algorithms 面试字符串专题回文、atoi、滑动窗口与双指针等高频算法题全解 字符串是算法面试中出现频率最高的考点之一围绕它衍生出回文判教程5分钟快速上手wvp-GB28181-pro国标视频平台部署指南5分钟快速上手wvp GB28181 pro国标视频平台部署指南 想要快速搭建一个兼容海康、大华、宇视等主流监控设备的国标视频平台吗wvp GB28181后端音视频前端上一篇Iosevka 26.0.0 变更深度解析字形变体重构、Unicode 字符扩展与连字规则调整下一篇Ingress NGINX Controller 实战示例大全认证、自定义、灰度发布与 TLS 配置指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
