串的定义

串（string）是由零个或多个字符组成的有限序列，又名叫字符串,一般记为:
空串(null string): 长度为0，可以用“”””或者ɸ表示 空格串: 只包含空格的串。 子串与主串：串中任意个数的连续字符组成的子序列称为该串的子串，相应的，包含子串的串称为主串。

串的比较

计算机中的常用字符是使用标准的 ASCII 编码，可以由 8 位二进制数表示一个字符，总共可以表示 256 个字符。但是 256 个字符不足以包含全世界的语言与文字，于是有了 Unicode 编码，常用 16 位二进制数表示一个字符，总共可以表示 2^16 个字符，约 65 万多个字符。为了和 ASCII 码兼容，Unicode 的前256个字符与 ASCII 码完全相同。

对于两个串不相等时，如何判定它们的大小呢？给定两个串：

两串相等： 当且仅当

认为s=t

两串不等： 当满足以下条件之一：

例如当s=“hap”，t=“happy”，就有s

例如当s=“happen”，t=“happy”，因为两串的前4个字母均相同，而两串第5 个字母（k值），字母e的ASCII码是101，而字母y的ASCII码是121，显然e

串的存储结构

顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全

朴素的模式匹配算法

定义

朴素模式匹配算法（Naive Pattern Matching Algorithm），也称为暴力匹配算法或简单匹配算法.通过逐个字符比较的方式，在主串中查找模式串的出现位置。当发生失配时，主串指针回退到上次匹配开始位置的下一个字符，模式串指针回到开头，重新开始匹配。

假设我们要从下面的主串 S=”hhgood” 中，找到模式串 T=”good”，通常需要以下步骤：

S 的第一位与 T 的第一位匹配失败：
S 的第二位与 T 的第一位匹配失败：
S 的第三位与 T 的第一位匹配成功，后续都匹配成功，则成功找到位置。

简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。

代码实现

int Index(const char *S, const char *T)
{
    int i, j;
    int s_len = strlen(S);
    int t_len = strlen(T);

    for(i = 0; i <= s_len - t_len; i++)  
    {
        for(j = 0; j < t_len; j++)
        {
            if(S[i + j] != T[j])
            {
                break;  // 失配时跳出内层循环
            }
        }
        if(j == t_len)      
        {
            return i;       // 完全匹配，返回起始位置
        }
    }

    return -1; // 未找到
}

时间复杂度

最好情况: O(n) – 第一次就匹配成功最坏情况: O(m×n) – 每次都在最后一个字符失配平均情况: O(n+m)

如果存在大量的匹配字符，这个算法，就显得太低效了。

KMP模式匹配算法

定义

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，由 Donald Knuth、Vaughan Pratt 和 James Morris 于1977年共同提出。KMP 算法通过预处理模式串来构建一个 next 数组（部分匹配表），利用这个数组在匹配失败时快速跳转，避免主串指针回退，从而提高字符串匹配的效率。

KMP 核心思想

避免重复比较
- 当匹配失败时，不从主串的下一个位置重新开始
- 利用已匹配的信息，跳过不可能匹配的位置
next 数组的作用
- 记录模式串中每个位置的”最长相等前后缀长度”
- 失配时告诉我们模式串应该跳转到哪个位置继续匹配

举例说明

定义主串 S = “abcdefgab”, 模式串 T = “abcdex”，符号 “↑” 代表匹配上，“X” 代表匹配失败，“i” 是 S 的指针，“j” 是 T 的指针，如下图所示。

按照朴素的模式匹配算法，会按 1-6 的步骤执行：

从第 1 步的时候可以看到，主串 S 和模式串 T 的前 “abcde” 匹配上了，但是 “f” 和 “x” 匹配失败，此时的主串 S 指针 i = 5，模式串 T 的指针 j = 5。
随着模式串 T 的往后移动，当模式串 T 的指针 i = 1 的时候，“b” ≠ “a”，在往后的 3-5 的步骤，我们发现，因为主串 S 的 “abcde” 和模式串 T 的 “abcde” 是相同的，那么步骤 2，3，4，5 不就是在和自己已经有的元素进行匹配吗？这不就是多余的操作吗？

这里就是理解 KMP 算法的关键了，如下图所示中，执行步骤 1 发现主串 S 和模式串 T 的前两个元素 “ab” 相等，并且模式串 T 的前两个元素 “a” 和 “b” 不相等，那么步骤 2 就相当于模式串 T 把自己的首位元素 “a” 和自己的第二个元素 “b” 比较，此举是多余的。

在来看第二个例子，如果 T 串后面也含有上个例子的首字符 “a” 这种情况。假设主串 S=“abcabcabc”，模式串 T=“abcabx”。

开始的匹配，前 5 个字符完全相等，第 6 个字符不相等，如图的步骤 1。根据上一个例子的结论，因为模式串 T 的 “a”, “b”, “c” 互不相等，并且与主串 S 的 “a”,”b”,”c” 相等，所以步骤 2， 3 都是多余操作。
因为模式串 T 的首位 “a” 与主串 T 的第 4 位 “a” 相等，第 2 位 “b” 与第 5 位 “b” 相等，在步骤 1 的时候，第 4 位 “a” 和第 5 位 “b” 是与主串 S 的相应位置匹配的，因此可以断定，模式串 T 的首字符 “a” 、第 2 位字符 “b” 与主串 S 的第 4 位字符和第 5 位字符也不需要比较了，所以步骤 4，5 也可以忽略。

通过上面2个例子可以发现，主串 S 的指针 i 值会从 1->6,或者 6->1，会不断回溯完成，这种回溯是可以不需要的，所以 KMP 模式匹配算法就是为了让这没必要的回溯不发生

next 数组定义

控制 i 值不变小，那么 j 值就要变化，j 值的变化取决于模式串 T 的结构是否有重复的问题。这里有个结论，j 值的多少取决于当前字符之前的串的前后缀相似度，把模式串 T 各个位置的 j 值的变化定义为一个数组 next, next 的长度就是 T 串的长度，有以下函数定义。

第一个条件：i = 0 时

含义： 第一个字符位置的特殊处理

位置 0 对应模式串的第一个字符 T[0]
由于没有前缀可以比较，设置为 -1 作为特殊标记
在匹配过程中，j = -1 表示需要重新开始匹配

第二个条件：存在相等前后缀时

条件分解：

0 <= k < i：前缀长度的取值范围
- k = 0：空前缀（长度为0）
- k 最大到 i-1：确保前缀不包含当前字符
T[0 … k-1] = T[i-k … i-1]：前缀等于后缀
- 前缀：T[0 … k-1]（从位置0开始，长度为k）
- 后缀：T[i-k … i-1]（到位置i-1结束，长度为k）

具体例子（$i = 4$，子串 “ABAB”）：

k = 0：前缀 “”，后缀 “”（空串相等）✓
k = 1：前缀 “A”，后缀 “B”（不相等）✗
k = 2：前缀 “AB”，后缀 “AB”（相等）✓
k = 3：前缀 “ABA”，后缀 “BAB”（不相等）✗

集合 = {0, 2}，max{0, 2} = 2，所以 next[4] = 2

第三个条件：其他情况

含义： 没有相等的非空前后缀

当上述集合只包含 {0}（即只有空前缀相等）
或者集合为空时
设置 next[i] = 0，表示没有可用的前缀信息

Next 数组推导例子：T = “ABABAC”

i = 0: 字符 ‘A’

条件: i = 0
结果: next[0] = -1

i = 1: 子串 “AB”

集合: {k | 0 ≤ k < 1, 且 T[0...k-1] = T[1-k...0]}
k = 0: 空串 = 空串 ✓
集合: {0}
结果: next[1] = max{0} = 0

i = 2: 子串 “ABA”

集合: {k | 0 ≤ k < 2, 且 T[0...k-1] = T[2-k...1]}
k = 0: 空串 = 空串 ✓
k = 1: T[0] = A, T[1] = B ❌
集合: {0}
结果: next[2] = max{0} = 0

i = 3: 子串 “ABAB”

集合: {k | 0 ≤ k < 3, 且 T[0...k-1] = T[3-k...2]}
k = 0: 空串 = 空串 ✓
k = 1: T[0] = A, T[2] = A ✓
k = 2: T[0…1] = AB, T[1…2] = BA ❌
集合: {0, 1}
结果: next[3] = max{0, 1} = 1

i = 4: 子串 “ABABA”

集合: {k | 0 ≤ k < 4, 且 T[0...k-1] = T[4-k...3]}
k = 0: 空串 = 空串 ✓
k = 1: T[0] = A, T[3] = B ❌
k = 2: T[0…1] = AB, T[2…3] = AB ✓
k = 3: T[0…2] = ABA, T[1…3] = BAB ❌
集合: {0, 2}
结果: next[4] = max{0, 2} = 2

i = 5: 子串 “ABABAC”

集合: {k | 0 ≤ k < 5, 且 T[0...k-1] = T[5-k...4]}
k = 0: 空串 = 空串 ✓
k = 1: T[0] = A, T[4] = A ✓
k = 2: T[0…1] = AB, T[3…4] = BA ❌
k = 3: T[0…2] = ABA, T[2…4] = ABA ✓
k = 4: T[0…3] = ABAB, T[1…4] = BABA ❌
集合: {0, 1, 3}
结果: next[5] = max{0, 1, 3} = 3

算法执行过程验证

步骤	i	j	T[i]	T[j]	判断	操作	next更新
初始	0	-1	–	–	–	next[0]=-1	–
1	0	-1	A	–	j==-1	i++,j++	next[1]=0
2	1	0	B	A	B≠A	j=next[0]=-1	–
3	1	-1	B	–	j==-1	i++,j++	next[2]=0
4	2	0	A	A	A=A	i++,j++	next[3]=1
5	3	1	B	B	B=B	i++,j++	next[4]=2
6	4	2	A	A	A=A	i++,j++	next[5]=3
7	5	3	C	B	C≠B	j=next[3]=1	–
8	5	1	C	B	C≠B	j=next[1]=0	–
9	5	0	C	A	C≠A	j=next[0]=-1	–
10	5	-1	C	–	j==-1	i++,j++	结束

最终结果

T = "ABABAC"
next = [-1, 0, 0, 1, 2, 3]

结果验证

i	子串	最长相等前后缀	长度	next[i]
0	“A”	无	–	-1
1	“AB”	空串	0	0
2	“ABA”	空串	0	0
3	“ABAB”	“A”	1	1
4	“ABABA”	“AB”	2	2
5	“ABABAC”	“ABA”	3	3

关键观察

next[i] 直接表示最长相等前后缀的长度
-1 是特殊标记，用于处理边界情况
算法通过递推方式构建，避免重复计算
回退机制确保找到所有可能的前后缀匹配

KMP 模式匹配算法实现

代码里面有详细的注释。

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

/**
 * @brief 计算模式串T的next数组
 * @param T 模式串
 * @param next next数组
 * @param j 模式串的前缀长度, 即数学函数定义中的 k
 * @param i 模式串的当前字符位置 
 * @details next数组用于KMP算法中，记录模式串的前缀信息
 * next[i]表示模式串T的前i个字符的最长相等前后缀的长度
 * 
 * next数组的计算过程如下：
 * 1. 初始化i=0, j=-1，next[0]=-1
 * 2. 遍历模式串T的每个字符
 * 3. 如果当前字符T[i]与前缀字符T[j]匹配，则i和j都向后移动，记录next[i+1]=j+1
 * 4. 如果不匹配，则将j回退到更短的前缀位置，继续尝试匹配
 * 5. 重复步骤2-4直到遍历完整个模式串
 * 
 */
void get_next(const char *T, int *next) 
{
    int len = strlen(T);
    int i = 0, j = -1;  next[0] = -1;   /* i: 当前字符位置, j: 前缀长度(-1表示无前缀) */

    next[0] = -1;                       /* 第一个字符没有前缀，设为-1 */

    while (i < len)                     /* 遍历模式串的每个位置 */
    {

        if (j == -1 || T[i] == T[j])    /* 情况1: j==-1(无前缀) 或 情况2: 当前字符与前缀字符匹配 */
        {
            ++i;                        /* 移动到下一个字符 */
            ++j;                        /* 前缀长度增加1(j从-1变0，或从当前值+1) */  
            next[i] = j;                /* next[i+1] = j+1：记录当前位置模式串T的前i个字符的最长相等前后缀的长度 */
        } 
        else                            /* 情况3: 当前字符与前缀字符不匹配，回退 */   
        {
            j = next[j];                /* 当前k不满足，尝试更小的k，利用已计算的结果快速回退，回退到更短的前缀位置，继续尝试匹配 */
        }
    }
}

/**
 * @brief KMP字符串匹配算法
 * @param S 主串（待搜索的字符串）
 * @param T 模式串（要查找的子串）
 * @return 匹配成功返回模式串在主串中的起始位置（从0开始），失败返回-1
 * @details KMP算法利用next数组避免主串指针回溯，提高匹配效率
 * 
 * 匹配过程：
 * 1. 计算模式串的next数组
 * 2. 使用两个指针i(主串)和j(模式串)进行匹配
 * 3. 匹配成功时，两指针都向后移动
 * 4. 失配时，主串指针不回退，模式串指针根据next数组跳转
 * 5. 当j达到模式串长度时，匹配成功
 */

int KMP_Match(const char *S, const char *T) 
{
    int slen = strlen(S);       /* 主串长度 */
    int tlen = strlen(T);       /* 模式串长度 */

    if (tlen == 0) return 0;    /* 空模式串匹配任意位置 */
    if (slen < tlen) return -1; /* 主串比模式串短，无法匹配 */

    /* 计算模式串的next数组 */
    int *next = (int*)malloc(tlen * sizeof(int));
    if (next == NULL) return -1; /* 内存分配失败 */

    get_next(T, next);          /* 调用前面实现的get_next函数 */

    int i = 0, j = 0;           /* i: 主串指针, j: 模式串指针 */

    while (i < slen && j < tlen) /* 当两个指针都未越界时继续匹配 */
    {
        if (j == -1 || S[i] == T[j]) /* 情况1: j==-1(模式串回到开头) 或 情况2: 字符匹配 */
        {
            ++i;                /* 主串指针向后移动 */
            ++j;                /* 模式串指针向后移动 */
        }
        else                    /* 情况3: 字符不匹配 */
        {
            j = next[j];        /* 模式串指针根据next数组跳转，主串指针不回退 */
        }
    }

    free(next);                 /* 释放next数组内存 */

    if (j >= tlen)              /* 模式串完全匹配 */
        return i - tlen;        /* 返回匹配起始位置 */
    else
        return -1;              /* 匹配失败 */
}

int main()
{
    char *str = "abcabcabcd";
    char *pat = "abcd";
    int pos = KMP_Match(str, pat);
    printf("pos = %d\n", pos);
    return 0;
}

运行结果

pos = 6

[Done] exited with code=0 in 2.561 seconds

复杂度分析

时间复杂度证明

总操作次数 = i增加次数 + j回退次数
- i最多增加m次（m为字符串长度）
- j最多回退m次（因为j最多增加m次）
因此总复杂度 = O(m)

空间复杂度

额外空间 = O(1)（不包括输出数组）

核心思想总结

化枚举为递推：避免重复计算
利用已知信息：从next[j]推导下一步
状态机思维：(i,j)表示当前匹配状态
失配回退：利用前缀信息快速跳转
边界特殊处理：用-1标记特殊状态

这种转换将O(m³)的朴素算法优化为O(m)的高效算法，体现了动态规划和状态机的思想。

应用场景

文本编辑器的查找功能：
- 查找替换功能：在文档中查找特定字符串
- 语法高亮：识别关键字、注释等语法元素
- 拼写检查：在词典中查找单词
搜索引擎的关键词匹配：
- 网页内容检索：在网页文本中查找关键词
- 索引构建：快速定位文档中的关键信息
- 相关性计算：统计关键词出现次数和位置
生物信息学中的序列比对
- 基因序列匹配：在DNA序列中查找特定基因片段
- 蛋白质序列对比：比较蛋白质序列的相似性
- 进化分析：寻找保守序列和突变点
入侵检测系统 (IDS)
- 恶意代码检测：在网络流量中查找病毒签名
- 攻击模式识别：检测SQL注入、XSS等攻击模式
- 异常行为分析：识别可疑的网络通信模式
反垃圾邮件
- 垃圾邮件特征检测：识别邮件中的垃圾信息关键词
- 钓鱼邮件识别：检测欺诈性邮件内容
音频处理
- 音频指纹识别：在音频流中查找特定音频片段
- 语音识别：识别语音中的关键词
通信协议解析
- 串口通信中查找帧头

适合KMP的场景：

长文本中的短模式匹配
需要避免回溯的实时系统
模式串有重复前缀的情况
需要多次使用同一模式串的场景

不太适合的场景：

极短的文本和模式（开销可能超过收益）
一次性匹配且模式很简单
需要模糊匹配的场景