数据结构--串（有KMP算法）

数据结构之串详解

一、串的定义与核心概念

串是数据结构中一种特殊的线性表，其特殊性体现在数据元素的类型被限定为字符。以下从多个维度详细解析串的核心概念：

1.1 串的基本定义

• 串的本质：由零个或多个字符组成的有限序列，通常记为 S = "a₁a₂...aₙ"（n≥0）。其中，S 为串名，aᵢ（1≤i≤n）为单个字符（可是字母、数字、标点等），n 为串的长度。例：S = "Data Structure" 是一个串，包含 14 个字符（空格也计入长度）。

• 特殊串的区分：

  • 空串：长度为 0 的串，记为 ""（不含任何字符）。

  • 空格串：由一个或多个空格组成的串，如

    " "

    （长度为 3）。

    注意：空串与空格串的本质区别 —— 空串无字符，空格串有字符（空格也是字符）。

1.2 子串与主串

• 子串：串中任意连续的字符组成的子序列。例如，串 "abcdef" 中，"bcd"、"f" 都是其子串。
• 主串：包含子串的原串。若 A 是 B 的子串，则 B 是 A 的主串。
• 位置定义：
  • 字符在串中的位置：从 1 开始计数（与数组下标从 0 开始不同）。例如，"hello" 中 'e' 的位置是 2。
  • 子串在主串中的位置：子串第一个字符在主串中的位置。例如，"cd" 在 "abcdef" 中的位置是 3。

1.3 串与线性表的关系

• 相同点：逻辑结构均为线性关系（每个元素除首尾外，有唯一前驱和后继）。
• 不同点：
  • 数据元素类型：串的元素只能是字符，线性表可是任意数据类型。
  • 操作对象：串的操作多以 “子串” 为单位（如拼接、截取），线性表多以 “单个元素” 为单位（如插入、删除单个元素）。

二、串的基本操作

串的操作围绕字符序列的处理展开，以下是常用基本操作的详细说明（假设有串 S、T、Sub 等）：

2.1 赋值与复制

• 赋值（StrAssign）：功能：将一个字符序列赋给指定串。示例：StrAssign(&S, "Algorithm") 执行后，S 的值为 "Algorithm"，长度为 9。
• 复制（StrCopy）：功能：将一个串的内容完整复制到另一个串。示例：若 S = "Hello"，执行 StrCopy(&T, S) 后，T 的值与 S 完全相同（T = "Hello"）。

2.2 判空与长度

• 判空（StrEmpty）：功能：判断串是否为空串（长度为 0）。返回值：空串返回 true，否则返回 false。示例：StrEmpty("") 返回 true，StrEmpty(" ") 返回 false（空格串非空）。
• 求长（StrLength）：功能：返回串中字符的个数（长度）。示例：StrLength("Python 3.9") 返回 8（包含空格和小数点）。

2.3 清空与销毁

• 清空（ClearString）：功能：将串变为空串（长度设为 0，不释放存储空间）。示例：ClearString(&S) 执行后，S 的值为 ""，原存储空间仍保留。
• 销毁（DestroyString）：功能：释放串占用的存储空间（彻底删除串）。注意：动态分配的串（如堆存储）必须调用此操作，避免内存泄漏。

2.4 拼接与截取

• 拼接（Concat）：功能：将两个串合并为一个新串。示例：S = "Hello"，T = "World"，执行 Concat(&R, S, T) 后，R = "HelloWorld"（长度为 10）。特殊情况：若拼接后长度超过存储上限（如定长存储），可能截断或报错。
• 取子串（SubString）：功能：从主串的指定位置截取长度为 len 的子串。参数：Sub（输出子串）、S（主串）、pos（起始位置）、len（子串长度）。约束：pos 需满足 1≤pos≤StrLength(S)，且 pos + len - 1≤StrLength(S)（否则截取失败）。示例：S = "abcdefgh"，SubString(&Sub, S, 3, 4) 执行后，Sub = "cdef"（从位置 3 开始，取 4 个字符）。

2.5 比较与定位

• 串比较（StrCompare）：功能：按字典序比较两个串的大小。规则：逐字符对比 ASCII 码，首个不同字符的 ASCII 差即为结果；若所有字符相同，则长度长的串更大。返回值：S > T 返回正数，S = T 返回 0，S < T 返回负数。示例：StrCompare("apple", "apply") 返回 -16（因第 4 个字符 'e'（101） < 'y'（121））。
• 定位（Index）：功能：查找模式串 T 在主串 S 中首次出现的位置。返回值：成功返回起始位置，失败返回 0。示例：Index("ababa", "aba") 返回 1（首个匹配从位置 1 开始）。

三、串的存储结构

串的存储需平衡空间效率与操作便捷性，常见存储方式有以下三种：

3.1 定长顺序存储

核心思想：用固定大小的数组存储字符，通过额外变量记录实际长度。

结构定义

#define MAX_LEN 255  // 预定义最大串长
typedef struct {
    char ch[MAX_LEN];  // 存储字符（下标从1开始，ch[0]闲置）
    int length;        // 串的实际长度（≤MAX_LEN）
} SString;

存储细节

• 字符从 ch[1] 开始存储，ch[0] 闲置（方便与位置编号对应，避免下标转换）。
• 长度由 length 直接记录，无需遍历数组计算（对比以 '\0' 结尾的字符串更高效）。

核心操作实现

1. 取子串（SubString）：

   bool SubString(SString &sub, SString s, int pos, int len) {
       // 检查截取范围是否越界
       if (pos < 1 || len < 0 || pos + len - 1 > s.length) {
           return false;  // 越界返回失败
       }
       // 复制字符到子串
       for (int i = 0; i < len; i++) {
           sub.ch[i + 1] = s.ch[pos + i];  // 子串从1开始存储
       }
       sub.length = len;  // 设置子串长度
       return true;
   }

2. 串比较（StrCompare）：

   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];  // 返回首个不同字符的ASCII差
           }
       }
       // 所有字符相同，返回长度差
       return s.length - t.length;
   }

优缺点

• 优点：随机访问效率高（通过下标直接访问字符），实现简单。
• 缺点：长度固定，超过 MAX_LEN 时需截断（可能丢失数据），空间利用率低（可能浪费未使用的数组空间）。

3.2 堆分配存储

核心思想：动态分配存储空间（长度按需调整），通过指针指向字符序列。

结构定义

typedef struct {
    char *ch;  // 指向动态分配的字符数组（基地址）
    int length;  // 串的实际长度
} HString;

存储细节

• 存储空间通过 malloc() 动态分配，长度由 length 记录。
• 使用后需通过 free() 释放空间，避免内存泄漏。

操作示例

// 初始化串并赋值
HString createString(const char *chars) {
    HString s;
    int len = strlen(chars);  // 计算字符序列长度
    s.ch = (char *)malloc((len + 1) * sizeof(char));  // 多分配1字节存'\0'（可选）
    if (s.ch == NULL) {
        exit(1);  // 分配失败退出
    }
    strcpy(s.ch, chars);  // 复制字符序列
    s.length = len;
    return s;
}

// 销毁串
void destroyString(HString *s) {
    free(s->ch);  // 释放空间
    s->ch = NULL;  // 避免野指针
    s->length = 0;
}

优缺点

• 优点：长度灵活（按需分配），空间利用率高，支持随机访问。
• 缺点：动态分配 / 释放内存开销较大，频繁操作可能影响效率。

3.3 链式存储（块链结构）

核心思想：用链表存储字符，每个节点（块）可存储多个字符（提高存储密度）。

结构定义

#define BLOCK_SIZE 4  // 每个块存储4个字符
typedef struct StringNode {
    char ch[BLOCK_SIZE];  // 块中字符（不足时用空字符填充）
    struct StringNode *next;  // 指向下一块
} StringNode, *String;

存储细节

• 每个节点存储 BLOCK_SIZE 个字符（如 4 个），最后一个块未填满的位置用空字符填充。
• 串的长度需额外记录（或遍历链表计算，效率低）。

优缺点

• 优点：无需连续存储空间，插入 / 删除字符时无需大量移动元素（只需调整指针）。
• 缺点：按位访问效率低（需遍历链表），存储密度仍低于顺序存储（每个节点含指针开销）。

四、串的模式匹配算法

模式匹配是串的核心操作，指在主串中查找模式串（子串）首次出现的位置。以下详解两种经典算法：

4.1 朴素模式匹配（暴力匹配）

核心思想：从主串起始位置开始，逐个对比主串与模式串的字符；若匹配失败，主串回溯到下一起始位置，模式串从头开始。

算法实现

int Index(SString S, SString T) {
    int i = 1;  // 主串指针（从1开始）
    int j = 1;  // 模式串指针（从1开始）
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            // 当前字符匹配，继续下一个
            i++;
            j++;
        } else {
            // 匹配失败，主串回溯，模式串复位
            i = i - j + 2;  // 主串指针移至下一起始位置
            j = 1;
        }
    }
    // 若模式串遍历完，返回起始位置；否则匹配失败
    return (j > T.length) ? (i - T.length) : 0;
}

示例解析

设主串 S = "ababcabcacbab"（长度 13），模式串 T = "abcac"（长度 5）：

1. 首次匹配：i=1, j=1 开始，前 3 个字符 'a','b','c' 匹配（i=4, j=4），但 S[4]='a' 与 T[4]='a' 匹配，i=5, j=5 时 S[5]='b' 与 T[5]='c' 不匹配。
2. 回溯：i = 5 - 5 + 2 = 2，j=1，从 S[2] 重新开始。
3. 重复上述过程，最终在 i=6 处匹配成功，返回 6 - 5 = 1？（实际需完整遍历，此处仅为简化示例）。

时间复杂度

• 最坏情况：O(n*m)（n 为主串长度，m 为模式串长度）。例如，主串为 "aaaaa"，模式串为 "aaab"，每次需对比 m 个字符才失败，共需 n-m+1 次对比。
• 最好情况：O(n)。例如，模式串第一个字符与主串所有字符均不匹配，只需遍历主串一次。

4.2 KMP 算法（改进版）

核心优化：匹配失败时，主串指针不回溯，仅通过模式串的 “最长相等前后缀” 确定下次匹配的起始位置（通过 next 数组实现）。

关键概念：最长相等前后缀

• 前缀：不包含最后一个字符的所有头部子串。例如，"abcab" 的前缀为 "a","ab","abc","abca"。
• 后缀：不包含第一个字符的所有尾部子串。例如，"abcab" 的后缀为 "b","ab","cab","bcab"。
• 最长相等前后缀长度：前缀与后缀中相同且最长的子串长度。例如，"abcab" 的最长相等前后缀为 "ab"，长度为 2。

next 数组的定义与求解

next[j] 表示模式串第 j 个字符匹配失败时，模式串应回溯的位置，规则：

1. next[1] = 0（第一个字符失败，模式串右移 1 位）；
2. next[2] = 1（第二个字符失败，回溯到第一个字符）；
3. 对于 j≥3：next[j] = 最长相等前后缀长度 + 1（若无相等前后缀，长度为 0，故 next[j] = 1）。

求解示例：模式串 T = "abaabc"（下标 1-6）

j（位置）	1	2	3	4	5	6
T [j]（字符）	‘a’	‘b’	‘a’	‘a’	‘b’	‘c’
前子串（T [1…j-1]）	-	“a”	“ab”	“aba”	“abaa”	“abaab”
最长相等前后缀长度	-	0	0	1	1	2
next[j]	0	1	1	2	2	3

• j=3：前子串 "ab" 无相等前后缀，长度 0 → next[3] = 0+1=1；
• j=4：前子串 "aba" 最长相等前后缀为 "a"（长度 1）→ next[4] = 1+1=2；
• 以此类推。

KMP 匹配过程

int Index_KMP(SString S, SString T, int next[]) {
    int i = 1;  // 主串指针（不回溯）
    int j = 1;  // 模式串指针
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            // j=0表示模式串需从头开始，或当前字符匹配，继续下一个
            i++;
            j++;
        } else {
            // 匹配失败，模式串回溯到next[j]
            j = next[j];
        }
    }
    // 模式串遍历完则匹配成功，返回起始位置
    return (j > T.length) ? (i - T.length) : 0;
}

时间复杂度

• 求 next 数组：O(m)（m 为模式串长度）；
• 匹配过程：O(n)（n 为主串长度）；
• 整体复杂度：O(n + m)，远优于朴素算法。

总结

串作为特殊的线性表，其操作和存储需结合字符序列的特性设计：

• 存储结构中，定长顺序存储适合长度固定场景，堆存储适合动态长度，链式存储适合频繁插入删除；
• 模式匹配中，KMP 算法通过 next 数组避免主串回溯，核心是理解 “最长相等前后缀” 的求解逻辑，大幅提升效率。

掌握串的定义、操作、存储及模式匹配算法，是后续处理文本数据（如字符串搜索、编辑）的基础。