串与KMP模式匹配：存储结构、基本操作、next数组手算

cinonu

43人浏览 · 2026-10-07 17:56:36

cinonu · 2026-10-07 17:56:36 发布

摘要：串是数据结构中内容受限的线性表，模式匹配是串的核心考点。本文系统梳理串的基本概念、三种存储结构、基本操作、朴素模式匹配与 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);              // 比较：S>T 返回 >0，S=T 返回 0，S<T 返回 <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] = 0，next[2] = 1

4.2.2 手算示例

以模式串 "abaabc" 为例：

j	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next[j]	0	1	1	2	2	3

以 j=5 为例：前 4 个字符为 "abaa"，最长相等前后缀为 "a"，长度 1，所以：

next[5] = 1 + 1 = 2

4.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(m+n)

相比朴素模式匹配的 O(mn)，KMP 有显著提升。

五、考点总结

考点	考察方式
串的基本概念	选择题
空串与空格串	易混淆选择题
串的存储结构	选择题
朴素模式匹配时间复杂度	选择题
KMP 的 next 数组	高频选择题
nextval 数组	进阶选择题