[数据结构] 05 - 串和 KMP 算法

以下是按要求处理后的文档内容:


5.1 - 串的定义和比较

5.1.1 - 串的定义

串(String)是由零个或多个字符组成的有限序列,又叫字符串;

  • 串中的字符数目称为串的长度(lenth);
  • 零个字符的串称为空串(nul string);
  • 串的子序列称为子串(substring);

5.1.2 - 串的比较

在计算机中,字符串的比较通常遵循字典序(Lexicographical Order)。比较的本质是逐个字符比较其ASCII码值。

情况一:前缀关系(一个字符串是另一个的前缀)

条件: n<mn < m 且 ai=bia_{i} = b_{i}(对于 i=1,2,…,ni = 1 , 2 , \ldots , n)

  • 例子:
    • s="hap"s = "\text{hap}"
    • t="happy"t = "\text{happy}"
    • 前三个字母 "hap" 完全相同,但 tt 更长,所以 s<ts < t。

情况二:字符差异(在某个位置出现了不同的字符)

条件: 存在某个位置 kk,使得前面的字符都相同,但在第 kk 个位置,ss 的字符小于 tt 的字符(即 ASCII 码更小)。

  • 例子:
    • s="happen"s = "\text{happen}"
    • t="happy"t = "\text{happy}"
    • 前4个字符 "happ" 相同;
    • 第5个字符:ss 是 'e',tt 是 'y'。
    • 比较 ASCII 码:'e' (101) < 'y' (121)。
    • 所以 s<ts < t。

5.2 - 串 ADT

5.2.1 - 数据对象和数据关系

  • 串的数据对象是由字符组成的有限集合;
    • 假设字符集为 Σ\Sigma,那么串的数据对象就是 Σ∗\Sigma^{*}(Σ\Sigma 上所有有限长度字符串的集合);
  • 串是一种线性结构,相邻元素具有前驱和后继关系。

5.2.2 - 基本操作示例

操作含义函数名(参数)
赋值将字符串常量赋给变量 SSStrAssign(&S, chars)
求串长返回串 SS 的字符个数StrLength(S)
串比较比较两个串StrCompare(S, T)
串连接将串 TT 连接到串 SS 的末尾,生成新串Concat(&NewS, S, T)
求子串返回串中从第 posp o s 个字符起、长度为 lenl e n 的子串SubString(&Sub, S, pos, len)
串定位若主串 SS 中存在与串 TT 相同的子串,返回它在主串中第一次出现的位置Index(S, T)
清空串将串 SS 清空为空串ClearString(&S)
判空判断是否为空串StrEmpty(S)

5.3 - 串的存储结构

5.3.1 - 顺序串(定长数组)

使用一组地址连续的存储单元来存储串的字符序列

#define MAXLEN 255  // 预定义最大串长为255
typedef struct {
    char ch[MAXLEN]; // 存储字符的数组,每个分量存一个字符
    int length;      // 串的实际长度
} SString;
  • 静态分配(存储在栈区内存),无法动态扩展;
  • 随机访问:可通过下标 O(1) 访问任意字符;
  • 空间浪费或溢出;
  • 记录长度:通常会维护一个长度,不依赖 \0。也可以用字符串第 0 为记录长度。

5.3.2 - 顺序串(动态数组)

为了解决定长数组容易溢出和空间浪费的问题,采用动态内存分配

typedef struct {
    char *ch;    // 指向动态分配的内存首地址(而不是固定数组)
    int length;  // 串的实际长度
} HString;
  • 动态分配: 使用 malloc 或 realloc 在堆内存中申请空间,方便扩容;
  • 随机访问:内存连续,所以仍支持随机访问;

5.3.3 - 块链串

采用链表的方式存储串。

  • 因为串的字符通常很多,如果每个节点只存一个字符(像普通单链表那样),会导致存储密度极低(指针占用的空间远大于字符本身);
  • 因此,块链串通常让每个节点存储多个字符(称为一个“块”)。

#define CHUNKSIZE 80 // 定义每个块的大小(节点中存放的字符个数)
 
typedef struct Chunk {
    char ch[CHUNKSIZE]; // 块内存储字符的数组
    struct Chunk *next; // 指向下一个块的指针
} Chunk;
 
typedef struct {
    Chunk *head, *tail; // 串的头指针和尾指针
    int length;         // 串的实际长度
} LString;
  • 链式存储: 内存不需要连续,通过指针链接各个块;
  • 不支持随机访问;
  • 适用场景: 适用于串非常长,经常需要进行插入、删除,而不常进行随机访问的场景。

5.5 - 模式匹配算法

一个字符串的子串定位操作称为【串的模式匹配(Pattern/String Matching)】

5.5.1 - 朴素模式匹配算法(BF 算法)

朴素模式匹配算法也叫暴力模式匹配算法(Naive Pattern Matching Algorithm / Brute-Force Algorithm, BF 算法),是更符合人的直觉的匹配算法。

一、思路

核心做法:主串和模式串从头开始比,一旦遇到不匹配的字符,主串指针回退(回溯)到本次匹配起点位置的下一个位置,模式串重新从头开始比。

例子:从主串 S = “goodgoogle” 中,找到子串 T = “google”


二、实现

C 语言(用字符串的第 0 位用来存储字符串的长度):

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0 */
/* 其中,T非空,1 <= pos <= StrLength(S) */
int Index(String S, String T, int pos)
{
    int i = pos;            /* i用于主串S中当前位置下标值,从pos位置开始匹配 */
    int j = 1;              /* j用于子串T中当前位置下标值 */
    while (i <= S[0] && j <= T[0])  /* 当i小于S的长度并且j小于T的长度时,循环继续 */
    {
        if (S[i] == T[j])   /* 两字母相等则继续 */
        {
            ++i;
            ++j;
        }
        else                /* 指针后退重新开始匹配 */
        {
            i = i - j + 2;  /* i退回到上次匹配首位的下一位 */
            j = 1;          /* j退回到子串T的首位 */
        }
    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}
  • j 的值表示已经成功匹配了 j - 1 个字符;
  • j > T[0] 说明子串 T 的所有字符都已经匹配成功,匹配成功后循环就会退出。

三、复杂度分析

朴素模式匹配算法的时间复杂度,取决于主串 S 和子串 T 的字符分布情况:

  • 最好情况: O(m),目标子串是串的前缀;
  • 最坏情况: O(n × m),其中 n 是主串 S 的长度(例如主串为 "0000000001",子串为 "0001",每次匹配都要到最后一位才失配并大幅回溯)。
  • 平均情况:平均情况取决于字符集的大小:
    • 自然语言文本字符种类多,第一位匹配成功的概率低,大部分不匹配在比较 1 个字符后就会发生,回溯距离很短,因此实际的运行效率接近 O(n + m);
    • 二进制/高重复数据(极小字符集,例如 DNA 序列)中,字符种类很少,匹配失败后的回溯幅度通常较大,时间复杂度接近最坏情况 O(n × m)。

空间复杂度:

  • O(1),仅需常数级的额外变量指针。

5.5.2 - KMP 模式匹配算法

D.E.Knuth、J.H.Morris 和 V.R.Pratt 研究了一个模式匹配法,可大幅避免重复遍历的情况,称为克努特-莫里斯-普拉特算法,简称 KMP 算法。

通过预分析模式串的结构,KMP 算法可将处理常规字符串的最坏时间复杂度从 O(n × m) 降低到 O(n + m)。

最浅显易懂的 KMP 算法讲解 - 哔哩哔哩
https://www.bilibili.com/video/BV1AY4y157yL

一、思路

核心思路:KMP 发现,主串指针不需要在失配后回溯。可以利用模式串已匹配的前缀信息,直接跳到一个合理的位置继续匹配。

  • “合理的位置”将由 next 数组确定,计算 next 数组是 KMP 算法的核心;
  • 也就是说,KMP 算法的核心思想就是主串指针 i 不回退,只移动串指针 j;而串指针 j 的回溯方式,由一个数组来决定。

【例子 1】主串 S = “abcdefgab...”,子串 T = “abcdex”

若使用朴素模式匹配法,需经历 6 步:

朴素模式匹配法的 6 个步骤

  • 前 5 个字符时,两串完全相等(图中 ①);
  • 到第 6 个字符时,出现不等,所以 i 需回溯到主串的第 2 个字符,重新匹配;
  • 从 i = 2 起,连续多次发生子串首字符('a')不匹配(图中 ②~⑤);

仔细观察可发现:

  • 对于子串 T 来说,首字符 'a' 与后续的 "bcdex" 都不一致;
  • 而在第一次比较时,"bcde" 与主串已经匹配,这说明 T 的首字符 'a' 不可能与主串的第 2 至 5 个字符一致;
  • 所以,步骤 ②~⑤ 都是多余的,可将子串 T 直接移动到与主串第 6 项('F')对齐,开始匹配。

从第 ① 步,可直接跳到第 ⑥ 步

步骤 ⑥ 要保留,因为不能从 T[6] ≠ S[6] 得到 T[1] ≠ S[6]。

【例子 2】主串 S = “abcababca...”,子串 T = “abcabx”

如果子串 T 后面也出现了 'a' (也就是有重复的字符)怎么办?

若使用朴素模式匹配法,也需经历 6 步:

朴素模式匹配法的 6 个步骤

  • 前 5 个字符时,两串完全相等(图中 ①);
  • 第 6 个字符时发生不等,回溯;
  • 根据刚才的经验,因为子串中 'a' 和其后的 "bc" 不等,而 ① 中 "bc" 又与主串匹配,所以步骤 ②~③ 是多余的,可直接跳到步骤 ④;

而通过仔细观察可发现:

  • 子串 T 的前缀是 "ab" ,其第 4~5 位也是 "ab",而 ① 中 "ab" 也发生了匹配;
  • 我们可推断,子串 T 的前缀与主串 S 的第 4~5 位一定也匹配;
  • 因此步骤 ④~⑤ 也是多余的,可直接跳到步骤 ⑥。


通过以上两个例子可发现:

  • 主串上的指针 i 确实不需要在失配后回溯;
  • 核心是合理地移动子串的指针 j (也就是回溯子串)。
  • 而子串指针 j 如何移动,取决于子串的结构,即子串字符重复的情况。

刚才的例子中:

  • 【例子 1】T 在 x 前没有任何重复,j 从 6 变成 1;
  • 【例子 2】T 在 x 之前是 "abab",前缀和后缀有 2 位相等,j 从 6 变成 3。

j 要回溯到的位置,好像与当前字符之前的串的前后缀相似度有关。也就是说,在模式匹配前,先对子串进行预分析,可使主串指针 i 在失配时无需回溯。

二、几种略有不同的 Next 数组定义

next 数组在不同的教材 / 视频中有很多不同定义,但其作用都一致:

next 数组:当模式串第 j 个字符发生失配时,子串要如何回溯。

并且,无论是哪种定义,它们要利用的信息,都是“最长的相同真前缀和真后缀”。(不等于整个串的前 / 后缀)

KMP 算法中的 next 数组主要有 3 种常见定义,此外还有一种优化版本 nextval。

以模式串 P = "ABABAC" 为例:

定义方式下标起点next 数组含义
① 考研 408 / 教材经典版1[0, 1, 1, 2, 3, 4]失配时,模式串应跳转到的位置(从 1 开始编号)
② -1 开头版0[-1, 0, 0, 1, 2, 3]失配时,模式串应跳转到的位置(从 0 开始编号)
③ 前缀长度版(LPS / π)0[0, 0, 1, 2, 3, 0]截至当前位置,最长相等真前后缀的长度
④ 优化版(nextval)1[0, 1, 0, 1, 0, 4]在①的基础上,跳过必然再次失配的位置

核心区别

定义方式失配时如何更新模式串指针 j
① 教材经典版j = next[j]
② -1 开头版j = next[j],但需特殊处理 j == -1
③ LPS / π 版j = lps[j - 1],前提是 j > 0
④ nextval 优化版j = nextval[j]
  • ① 和②本质相同,主要区别是下标从 1 还是 0 开始。
  • ③记录的是前后缀长度,而不是直接记录失配位置;因此使用时通常需要 j - 1。
  • ④并不是独立的前后缀定义,而是对经典 next 数组的优化。

三、实现 getNext() 函数

前缀长度版定义(LPS 定义)是比较直观、适合理解的一种 Next 数组定义方式,本文使用这种定义方式。

1. LPS 定义

LPS 定义的核心思想:对于模式串的每一个位置,计算截至该位置的子串中,最长相等真前缀与真后缀的长度。

对于 LPS 定义,**Next[j] = T[0 ... j] 的最长相等真前后缀长度**。

  • 前缀:从字符串开头开始的连续子串。
  • 后缀:到字符串末尾结束的连续子串。
  • 真前缀、真后缀:不能是整个字符串本身,可以为空串。

2. 手算 Next 数组

以模式串 ABABCABAB 为例:

i子串 (P[0 … i])最长相等真前后缀Next[i]
0A无0
1AB无0
2ABAA1
3ABABAB2
4ABABC无0
5ABABCAA1
6ABABCABAB2
7ABABCABAABA3
8ABABCABABABAB4

所以:Next = [0, 0, 1, 2, 0, 1, 2, 3, 4] 。

虽然结果正确,但这个过程存在问题:

  • 每次都比较全部的前后缀,效率不高;
  • 实际上,可利用已有的 Next 值,快速计算后面的值。

3. 递推求 Next 数组

在计算 Next[i] 时,我们一定已经算出 Next[i - 1]。

令 j = Next[i - 1],j 的含义就是在加入新字符 P[i] 之前,已经存在长度为 j 的相等真前后缀。

接下来只需比较 P[j] 和 P[i]:

CASE 1: P[j] == P[i]

如果 P[j] == P[i],则 Next[i] = j + 1;

  • 因为 j 表示已经比较过的相等真前后缀的长度,所以 P[j] 就是“已比较相同的前缀的下一个字符”(因为下标从 0 开始);
  • 如果 P[i](当前字符,也是原相同后缀的下一个字符)与 P[j] 相等,则说明原本的相同真前 / 后缀可延长一位;
  • 因此,令 Next[i] = j + 1,避免了重复的比较。

【例子】ABAB 再加一个 A

  • 只需比较一次 P[2] == P[4] ,相等前后缀就可以从 AB 变成 ABA。

CASE 2: P[j] != P[i]

如果 P[i] != P[i],则尝试让 j = Next[j - 1];
然后重新比较,直到 P[j] == P[i] 或 j = 0;

  • 如果 P[i] 和 P[j] 不一样,说明最长的相等前后缀无法继续延长;
  • 但是,最长的相等前后缀无法继续扩展,不代表更短的相等前后缀也无法扩展,我们可以尝试在更短的前后缀的基础上延长;
  • 而 Next[j-1] 恰好能找到下一个值得尝试的长度(例子中说明原因)
  • 因此,令 j = Next[j - 1],并再次比较 P[i] 和 P[j];
  • 如果相等,则 next[i] = ++j,如果不等,则重复这个操作直到 j = 0(j = 0 时还要再比最后一次)。

【例子】ABAABA 再加一个 C

  1. 令 j = Next[i = 1] = 3,并比较 P[i] 和 P[j](A 和 C),发现不等,也就是原本的最长相同真前后缀(ABA),无法继续延长;

    我们现在要寻找 ABAABA 这个字符串中,除了最长的 ABA 之外,第二长的相等真前后缀;

  1. 如图,令 j = Next[j - 1]。

    我们发现,Next[j - 1] 的值,就是“第二长的相等真前后缀”,也就是下一个值得进行比较的长度,因为“前缀的前缀”一定与“后缀的后缀”一致(图中红色 A);

  2. 再一次比较 P[i] 和 P[j](B 和 C),发现仍不等;

  1. 重复步骤,再一次令 j = Next[j - 1],此时 j = 0(即终止条件);
  2. 比较 P[i] 和 P[j](A 和 C),发现不等,因此 Next[6] = 0;

4. 递推求 Next 数组的代码实现

用上述方法求 LPS 定义的 Next 数组(C 语言):

 
#include <stdio.h>
#include <string.h>
 
void getNext(const char P[], int Next[]) {
    int m = strlen(P);
    int j = 0;
 
    if (m == 0) return;
 
    // 首个字符的 next 值为 0
    Next[0] = 0;
 
    for (int i = 1; i < m; i++) {
        while (j > 0 && P[i] != P[j]) {
            j = Next[j - 1];
        }
 
        // j = 0 是终止条件,达到此条件后仍需再进行一次判断
        if (P[i] == P[j]) {
            j++;
        }
 
        Next[i] = j;
    }
}

这份代码如何保证每次进入 for 循环时,j 的值都是 Next[i-1] ?

j 在每次 for 循环结束时,都等于当前计算出来的 Next[i],而下一次循环开始时 i++,且 j 不会被重新初始化,自然就有 j = Next[i - 1]。

四、实现完整 KMP 代码

 
#include <stdio.h>
#include <string.h>
 
// 构造 Next 数组
void getNext(const char P[], int Next[]) {
    ...
}
 
// KMP 字符串匹配,T 为主串,P 为待匹配子串 
int KMP(const char T[], const char P[]) {
    int n = strlen(T);
    int m = strlen(P);
 
    if (m == 0) return 0;
 
    int Next[m];
    getNext(P, Next);
 
    int j = 0;
 
    for (int i = 0; i < n; i++) {
        while (j > 0 && T[i] != P[j]) {
            j = Next[j - 1];
        }
 
        if (T[i] == P[j]) {
            j++;
        }
 
        if (j == m) {
            return i - m + 1;
        }
    }
    // 没有找到
    return -1;
}
 
int main() {
    char T[] = "ABABCABCACBAB";
    char P[] = "ABCAC";
 
    int pos = KMP(T, P);
 
    if (pos != -1) {
        printf("匹配成功,起始下标:%d\n", pos);
    } else {
        printf("匹配失败\n");
    }
 
    return 0;
}

可以发现 getNext() 和 KMP() 的核心结构几乎完全一样:

操作getNext()KMP()
比较字符P[i] 与 P[j]T[i] 与 P[j]
匹配失败j = Next[j-1]j = Next[j-1]
匹配成功j++j++
最终操作Next[i] = jj == m 时,返回位置

因为两者实际上都在做同一件事:利用已经匹配的前缀信息,在失配时寻找下一个可能匹配的位置。

while (j > 0 && T[i] != P[j]) {
    j = Next[j - 1];
}

此时 j 表示模式串 P 中已经成功匹配的字符数量,因为每匹配成功一个字符 j 向前移动一位。

发生失配后:

  • 主串下标 i 不回退;
  • 模式串通过更新 j,尝试更短的已匹配前缀;
  • 通过循环,最终 j 会更新为可以继续匹配的位置,或 j = 0。