摘要串是数据结构中内容受限的线性表模式匹配是串的核心考点。本文系统梳理串的基本概念、三种存储结构、基本操作、朴素模式匹配与 KMP 算法并详细讲解 next 数组手算方法适合期末复习与 408 考研冲刺。关键词数据结构、串、字符串、KMP、next数组、模式匹配、408考研适合读者数据结构初学者、考研 408 备考同学、正在复习串与 KMP 的同学。阅读收获掌握串的存储结构与基本操作理解朴素匹配的不足能独立手算 next 数组并写出 KMP 匹配代码。目录一、串的基本概念二、串的存储结构三、串的基本操作四、串的模式匹配五、考点总结六、总结一、串的基本概念1.1 定义串就是字符串是由零个或者多个字符组成的有限序列一般记为S a1a2...an其中n ≥ 0。串是一种内容受限的线性表其数据对象限定为字符集。1.2 术语术语定义字串串中任意多个连续的字符组成的子序列主串包含子串的串字符在串中的位置某个字符在串中的序号空格串空格也是字符空格串不是空串串相等两个串的长度相等并且对应位置的字符相等易混淆点空串是长度为 0 的串空格串是包含空格的串二者完全不同。1.3 基本操作Concat(T, S1, S2); // 串联接用 T 返回 S1 和 S2 连接成的新串 SubString(Sub, S, pos, len); // 求子串返回 S 第 pos 个字符起长度为 len 的子串 Index(S, T); // 定位返回 T 在 S 中第一次出现的位置不存在返回 0 StrCompare(S, T); // 比较ST 返回 0ST 返回 0ST 返回 0二、串的存储结构2.1 定长顺序存储使用静态数组实现串的长度有上限。2.1.1 位序与下标的关系方法一从下标 0 开始存储位序与下标相差 1。方法二从下标 1 开始存储位序与下标相同下标 0 的空间可用来存储串长。方法三在字符末尾添加结束标志\0但获取串长需要遍历。默认存储方式从下标 1 开始存储字符牺牲下标 0 的空间并额外定义一个整型变量记录串长。#define MAXLEN 255 // 默认存储方式从下标 1 开始存储字符 typedef struct { char ch[MAXLEN]; // ch[0] 不用 int length; // 串长 } SString;2.2 堆分配存储使用动态数组实现按需分配存储空间。与顺序表的动态分配方式相同灵活性更高。typedef struct { char *ch; // 按串长分配ch 指向串的首地址 int length; // 串长 } HString; HString str; str.ch (char *)malloc(MAXLEN * sizeof(char)); str.length 0;2.3 链式存储用链表存储串每个结点可以存一个或多个字符。为了提高存储密度通常每个结点存多个字符。typedef struct StringNode { char ch[4]; // 每个结点存 4 个字符 struct StringNode *next; } StringNode, *String;链式存储的串在模式匹配中效率较低实际中顺序存储更常用。三、串的基本操作3.1 求子串bool SubString(SString Sub, SString S, int pos, int len) { if (pos len - 1 S.length) return false; for (int i pos; i pos len; i) Sub.ch[i - pos 1] S.ch[i]; Sub.length len; return true; }3.2 比较串 S 和串 T 的大小int StrCompare(SString S, SString T) { for (int i 1; i S.length i T.length; i) { if (S.ch[i] ! T.ch[i]) return S.ch[i] - T.ch[i]; } return S.length - T.length; }3.3 定位操作int Index(SString S, SString T) { int i 1, n S.length, m T.length; SString sub; while (i n - m 1) { SubString(sub, S, i, m); if (StrCompare(sub, T) ! 0) i; else return i; } return 0; }四、串的模式匹配4.1 简单模式匹配将主串中与模式串相同长度的子串依次对比一旦某个字符不匹配立即放弃当前子串转而检索下一个子串直到找到完全匹配的子串或遍历所有子串。int Index(SString S, SString T) { int k 1; int i k, j 1; while (i S.length j T.length) { if (S.ch[i] T.ch[j]) { i; j; } else { k; i k; j 1; } } if (j T.length) return k; // 匹配成功返回起始位置 else return 0; // 匹配失败 }4.1.1 时间复杂度分析子串长为n主串长为m情况时间复杂度匹配成功的最好时间复杂度o(n)匹配成功的最坏时间复杂度o(m n)匹配失败的最好时间复杂度o(m)匹配失败的最坏时间复杂度o(m n)缺点主串指针需要频繁回退没有利用已经匹配过的信息效率低下。4.2 KMP 算法——让模式匹配拥有记忆4.2.1 核心原理利用匹配失败时已知的前缀信息跳过不必要的比较。将模式串的“记忆点”存入一个数组称为next数组。next 数组定义令S为模式串前j-1个字符组成的子串则next[j] S 的最长相等前后缀长度 1特别地next[1] 0next[2] 14.2.2 手算示例以模式串abaabc为例j123456模式串abaabcnext[j]011223以j5为例前 4 个字符为abaa最长相等前后缀为a长度 1所以next[5] 1 1 24.2.3 求 next 数组代码void get_next(SString T, int next[]) { int i 1, j 0; next[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; next[i] j; } else { j next[j]; } } }4.2.4 KMP 匹配代码int Index_KMP(SString S, SString T, int next[]) { int i 1, j 1; while (i S.length j T.length) { if (j 0 || S.ch[i] T.ch[j]) { i; j; } else { j next[j]; // 模式串回溯主串指针不动 } } if (j T.length) return i - T.length; // 匹配成功 else return 0; }4.2.5 时间复杂度求 next 数组O(n)KMP 匹配过程O(m)总时间复杂度O(mn)相比朴素模式匹配的O(mn)KMP 有显著提升。五、考点总结考点考察方式串的基本概念选择题空串与空格串易混淆选择题串的存储结构选择题朴素模式匹配时间复杂度选择题KMP 的 next 数组高频选择题nextval 数组进阶选择题易错点空串长度为 0空格串长度 ≥ 1。串比较先比较字符再比较长度。KMP 中主串指针不回退模式串指针回退到next[j]。next 数组手算时注意取的是前j-1个字符的最长相等前后缀。六、总结串的核心在于存储结构和模式匹配定长顺序存储简单但不灵活堆分配存储更灵活。朴素模式匹配思路简单但最坏时间复杂度高。KMP 利用 next 数组记忆前缀信息将时间复杂度优化到O(mn)。建议复习时多手算几个模式串的 next 数组考试时才能快速准确作答。如果觉得本文对你有帮助欢迎点赞 收藏 关注。