Loading... ## 基本知识 ### 定义 串，即字符串 (String) 是由零个或多个**字符**组成的**有限序列**。 - 子串：串中任意个 (可为 0 ) **连续的**字符组成的子序列。 - 主串：包含子串的串。 - 字符在主串中的位置：字符在串中的序号。(从 1 开始) - 子串在主串中的位置：子串的第一个字符在主串中的位置。(从 1 开始) - 空串和空格串不是同一个东西。 串是一种特殊的线性表，数据元素之间呈线性关系。 串的数据对象限定为字符集 (如中文字符，英文字符，数字字符，标点字符等) ### 基本操作 串的基本操作，如增删改查通常**以子串为操作对象**。 - 赋值 - 复制 - 判空 - 求串长 - 清空 - 销毁 - 连接。可能有存储空间扩展的问题。 - 求子串 - 定位。返回一个串 `T` 在主串 `S` 中第一次出现的位置。 - 比较。从第一个字符开始往后一次对比，先出现更大字符的串就更大。长串的前缀与短串相同时，长串更大。 ### 编码 采用不同编码方式每个字符占用空间不同，做题中默认每个字符占 1B 即可。 ## 存储结构 ### 顺序存储 静态数组实现 (定长顺序存储)： ```c++ typedef struct { char ch[MAX_LEN]; int length; } SString; ``` 动态数组实现 (堆分配存储)： ```c++ typedef struct { char *ch; int length; } HString; ``` ### 链式存储 ```c++ typedef struct StringNode { char ch; struct StringNode *next; } StringNode, *String; ``` 此方式存储密度低，因为每个字符占用空间仅 1B ，而指针需要 4B。 因此推荐每个节点存储多个字符： ```c++ typedef struct StringNode { char ch[NODE_LEN]; struct StringNode *next; } StringNode, *String; ``` 字符串不为一个节点长度的整数倍时，可以使用一些占位符补充。 ### 基本操作 - 求子串 - 串的比较 - 求串在主串中的位置 ## 朴素模式匹配算法 字符串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。 朴素模式匹配算法：将主串中所有长度为 $m$ 的子串依次与模式串进行对比，直到找到一个完全匹配的子串，或与所有的子串都不匹配位置。 - 最多匹配 $n - m + 1$ 次 最坏情况下每个子串都要对米 $m$ 个字符，共 $n - m + 1$ 个子串，因此朴素算法时间复杂度为 $O((n - m + 1) m)$ 。大部分时候 $n >> m$ ，因此最终时间复杂度为 $O(mn)$ 。 ### KMP 算法 放个之前写过的文章吧： https://blog.domineto.top/algorithm/kmp.html 简单描述一下，KMP 算法是朴素算法的改进版本。举个例子，对于模式串 `abdcab` ，若在主串的第 $i$ 个字符开始匹配，且模式串的最后一个字母匹配失败了，按照朴素算法就应该继续从 $i + 1$ 继续匹配。但通过之前的匹配我们已经知道了主串中 $i$ 到 $i + 4$ 的字符为 `abdca` ，很容易发现 $i + 3$ 及之前的字符都不可能匹配上模式串，因此我们只需要继续从 $i + 4$ 开始看即可。 #### 手算 next 数组 在不匹配的位置前画一条分界线，模式串一步步往后退，直到分界线之前能匹配上，或模式串完全跨过分界线位置。此时分界线后是第几个字符，`next` 数组值就是多少。 下图举例在第六个位置匹配失败的情况下的做法：  模式串向右移动直到分界线前能匹配上 (至少移动一个)：  分界线后是第四个字符，因此 `next[6]` 应该为 4 。 #### 优化 next 数组 在模式串 `abdcab` 中，若匹配时发现第六个字母不匹配，按照上述方法求出 `next[6]` 应该为 1 。但很明显第六个字符肯定不为 `b` ，所以可以优化一下，将 `next[6]` 设为 0 。题目中常把这种优化后的 `next` 数组称为 `nextval` 数组。 **由 `next` 数组求出 `nextval` 数组**： ```c++ nextval[1] = 0; for (int j = 2; j < T.length; j++) { if (T.ch[next[j]] == T.ch[j]) nextval[j] = nextval[next[j]]; else nextval[j] = next[j]; } ``` 最后修改：2024 年 05 月 07 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏