当前位置：首页 > web >正文

数据结构之串

web 2025/5/11 3:34:12

一、串的定义与基本概念

1. 串的定义

定义：串是由零个或多个字符组成的有限序列，记作 s="a1a2…an"，例如 "data structure"、"123" 等。

空串：无任何字符，长度为 0，用 "" 表示，例如短信内容为空时即为空串。
空格串：由一个或多个空格组成，有长度，例如 " "（3 个空格）。
子串与主串：子串是主串中连续字符序列。
- 生活实例：回文诗 “上海自来水来自海上” 是一个串，其正读和反读相同，体现了串的逆序特性；英文单词 “friend” 中，“end” 是子串，“friend” 是主串。

2. 串的比较

规则：基于字符的 ASCII/Unicode 编码逐个比较，直到找到首个不同字符或遍历完较短串。

例 1："apple" vs "apricot"，前两个字符 “ap” 相同，第三个字符 “p”（ASCII 112）<“r”（ASCII 114），故 "apple" < "apricot"。
例 2："abc" vs "ab"，前两个字符相同，短串先遍历完，故 "abc" > "ab"。

二、串的抽象数据类型（ADT）

基本操作

赋值：将一个串的内容复制到另一个串。
比较：逐个字符按ASCII码值比较，决定串的大小关系。
连接：将两个串首尾相连，形成新串。
求子串：从主串的指定位置截取固定长度的子串。
替换：将主串中某子串替换为另一个串。
插入：在指定位置插入子串。
删除：删除主串中指定位置的子串。

生活实例：微信聊天时，发送前编辑文字（赋值）、转发消息（复制）、撤回消息（清空），以及搜索聊天记录中的关键词（定位），都是串操作的典型应用。

三、串的存储结构

1. 顺序存储

用数组存储，如 C 语言中用 char str[100] 存储字符串。
优缺点：
- 优点：随机访问快（如取第 5 个字符直接通过下标）。
- 缺点：插入 / 删除需移动元素，可能溢出。
生活实例：手机短信长度限制（如 70 字），若输入超过，需截断或分段，类似顺序存储的固定容量限制。

2. 链式存储

用链表结点存储字符，每个结点可存多个字符以减少空间浪费。
优点：动态灵活，插入 / 删除方便（如聊天记录不断新增，无需预先分配固定长度）。
缺点：随机访问慢，需遍历。

四、模式匹配算法

1. 朴素模式匹配算法

思路：从主串每个位置开始，逐个字符匹配子串，最坏时间复杂度 O((n−m+1)×m)。
生活实例：在一本小说中查找 “英雄” 一词，每次从当前位置开始逐字对比，若每次都在子串末尾发现不匹配（如主串是 “英雄气短”，子串是 “英雄豪杰”），需多次回溯，效率低。

2. KMP 算法

核心思想：利用部分匹配信息避免不必要的回溯。
部分匹配表（Next数组）：
- 定义：next[j] 表示模式串前 𝑗j 个字符的最长公共前后缀长度。
- 计算示例（模式串 "ABCDABD"）：
  
  j 0 1 2 3 4 5 6
  模式串 A B C D A B D
  next[j] -1 0 0 0 0 1 2
- 匹配过程：当字符失配时，模式串右移 𝑗−𝑛𝑒𝑥𝑡[𝑗]j−next[j] 位。
时间复杂度：𝑂(𝑛+𝑚)O(n+m)，显著优于朴素算法。

j	0	1	2	3	4	5	6
模式串	A	B	C	D	A	B	D
next[j]	-1	0	0	0	0	1	2

六、KMP算法的实现细节

Next数组的推导：
- 初始化 next[0] = -1。
- 通过递推计算每个位置的 next[j]，利用已计算的 next 值减少重复比较。
优化Next数组：
- 若 pattern[j] == pattern[next[j]]，则 nextval[j] = nextval[next[j]]，进一步减少比较次数。
- 代码示例：

#include <iostream>
#include <string>
#include <vector>// 朴素模式匹配算法
int naivePatternMatching(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();for (int i = 0; i <= n - m; ++i) {int j;for (j = 0; j < m; ++j) {if (text[i + j] != pattern[j]) {break;}}if (j == m) {return i;}}return -1;
}// 计算next数组
void computeNext(const std::string& pattern, std::vector<int>& next) {int m = pattern.length();int len = 0;next[0] = 0;int i = 1;while (i < m) {if (pattern[i] == pattern[len]) {len++;next[i] = len;i++;}else {if (len != 0) {len = next[len - 1];}else {next[i] = 0;i++;}}}
}// KMP算法
int kmpPatternMatching(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();std::vector<int> next(m);computeNext(pattern, next);int i = 0;int j = 0;while (i < n) {if (pattern[j] == text[i]) {j++;i++;}if (j == m) {return i - j;}else if (i < n && pattern[j] != text[i]) {if (j != 0) {j = next[j - 1];}else {i = i + 1;}}}return -1;
}int main() {std::string text = "ABABDABACDABABCABAB";std::string pattern = "ABABCABAB";// 朴素模式匹配int naiveIndex = naivePatternMatching(text, pattern);if (naiveIndex != -1) {std::cout << "朴素模式匹配: 模式串在主串中的位置是 " << naiveIndex << std::endl;}else {std::cout << "朴素模式匹配: 未找到模式串" << std::endl;}// KMP模式匹配int kmpIndex = kmpPatternMatching(text, pattern);if (kmpIndex != -1) {std::cout << "KMP模式匹配: 模式串在主串中的位置是 " << kmpIndex << std::endl;}else {std::cout << "KMP模式匹配: 未找到模式串" << std::endl;}return 0;
}

查看全文

http://www.xdnf.cn/news/4642.html