串的定义

串（String）是由零个或多个字符组成的有限序列，通常用于表示文本信息。在计算机科学中，串是一种基本的数据结构，广泛应用于文本处理、数据存储和通信协议等领域。

串的数学表示

串可以形式化地表示为： [ S = a_1a_2a_3 \ldots a_n ] 其中：

• ( S ) 是串的名称。
• ( a_i ) 是串中的第 ( i ) 个字符，属于某个字符集（如ASCII或Unicode）。
• ( n ) 是串的长度，当 ( n = 0 ) 时称为空串。

串的基本特性

1. 长度：串中字符的数目称为串的长度。空串的长度为0。
2. 子串：串中任意连续的字符组成的子序列称为子串。
3. 主串：包含子串的串称为主串。
4. 位置：字符在串中的序号称为该字符的位置（从1开始计数）。
5. 相等：两个串的长度相等且对应位置的字符完全相同，则称这两个串相等。

串的存储结构

1. 定长顺序存储：使用固定长度的数组存储串，超出部分截断。

   #define MAX_LEN 100
   typedef struct {
       char ch[MAX_LEN];
       int length;
   } SString;
   

2. 堆分配存储：动态分配内存空间存储串，长度可灵活调整。

   typedef struct {
       char *ch;
       int length;
   } HString;
   

3. 链式存储：使用链表存储串的每个字符，适合频繁插入和删除操作。

   typedef struct StringNode {
       char ch;
       struct StringNode *next;
   } StringNode;
   

串的操作

串的常见操作包括：

• 赋值：将一个串的内容复制到另一个串。
• 连接：将两个串首尾相连形成新串。
• 求子串：从主串中截取指定位置的子串。
• 比较：按字典序比较两个串的大小。
• 模式匹配：在主串中查找子串的位置（如KMP算法）。

串的应用场景

1. 文本编辑：串用于表示文档内容，支持查找、替换等操作。
2. 编译器设计：词法分析阶段将源代码分解为标识符、关键字等串。
3. 数据存储：数据库中的字符串类型字段存储文本信息。
4. 网络协议：HTTP请求和响应中的头部信息以串形式传输。

串匹配问题定义

给定主串 s（长度为 n）和模式串 p（长度为 m），找到 p 在 s 中首次出现的起始位置，未找到返回 -1。

暴力算法（Brute-Force）

匹配逻辑
逐个尝试主串的每个位置作为匹配起点，若当前字符匹配失败，主串指针回退到上一轮起始位置的下一个字符，模式串指针归零。

伪代码实现

i = 0, j = 0  
while i < n && j < m:  
    if s[i] == p[j]:  
        i++, j++  
    else:  
        i = i - j + 1  // 主串回退到下一起始点  
        j = 0          // 模式串重置  
return j == m ? i - j : -1  

缺点

• 主串指针频繁回溯，重复比较次数多。
• 最坏时间复杂度为 O(n*m)（例如 s="aaaab"，p="aab"）。

KMP算法核心思想

核心优化
主串指针 i 永不回退，通过预处理模式串的 next 数组，使模式串指针 j 在失败时智能跳转，跳过不必要的比较。

next数组定义与作用

定义
next[j] 表示模式串 p[0..j-1] 中最长相等真前缀和真后缀的长度（真前缀/后缀不包含整个字符串）。

作用
当 p[j] 匹配失败时，j 跳转到 next[j] 而非归零，避免重复比较已知匹配部分。

next数组构造方法

实现代码

vector<int> buildNext(string& p) {
    int m = p.size();
    vector<int> next(m, 0);
    int len = 0;  // 当前最长相等前后缀长度
    int i = 1;
    while (i < m) {
        if (p[i] == p[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) len = next[len - 1];
            else next[i++] = 0;
        }
    }
    return next;
}

逻辑说明

• len 记录当前最长匹配长度，i 遍历模式串。
• 若 p[i] == p[len]，则 len 和 i 同时后移。
• 若不等且 len > 0，回退 len 至 next[len-1]；否则 next[i] 置零。

KMP匹配过程

实现代码

int kmp(string s, string p) {
    int n = s.size(), m = p.size();
    auto next = buildNext(p);
    int i = 0, j = 0;
    while (i < n) {
        if (s[i] == p[j]) i++, j++;
        if (j == m) return i - j;  // 匹配成功
        else if (i < n && s[i] != p[j]) {
            if (j != 0) j = next[j - 1];  // 利用next跳转
            else i++;
        }
    }
    return -1;
}

关键操作

• 匹配成功时同步移动 i 和 j。
• 匹配失败时，若 j > 0，跳转 j 至 next[j-1]；否则仅移动 i。

算法对比

对比项	Brute-Force	KMP
主串指针行为	失败时回退	永不回退
模式串指针行为	失败归零	跳转到 next[j]
时间复杂度	最坏 O(n*m)	最坏 O(n+m)
空间复杂度	O(1)	O(m)（存储next数组）
适用场景	短模式串或简单匹配	长文本或高频匹配

关键区别总结

• BF算法：简单但效率低，主串和模式串均需频繁回溯。
• KMP算法：通过预处理 next 数组避免主串回溯，利用部分匹配信息优化跳转。