1. 串
1. 串的定义
- 串:零个或多个 字符 组成的 有限 序列
- 串的长度:串中字符的个数
- 空串:长度为 0 的串
""
- 非空串:
String = "c1c2c3...cn"
- 串名:
String
- 定界符:
" "
- 数据元素:字符
ci
- 串名:
- 主串:包含子串的串
- 子串:串中任意个 连续 的字符组成的子序列
- 子串的位置:子串中的第一个字符在主串中的序号
- 串相同:串长度相同并且各个对应的字符也相同
2. 串的存储设计
- 顺序串:采用连续设计存储的字符序列
-
存储形式
-
非压缩形式
-
压缩形式
-
-
如何表示串的长度
- 用一个变量记录实际长度
- 在串尾增加一个不会在串中出现的特殊字符作为终止符,例如
'\0'
-
- 链接串:采用链接存储设计来存储串。串的链式存储结构和线性表的串的链式存储结构类似,采用单链表来存储串,结点的构成是:
data
域:存放字符,data
域可存放的字符个数称为结点的大小;next
域:存放指向下一结点的指针。
若每个结点仅存放一个字符,则结点的指针域就非常多,造成系统空间浪费,为节省存储空间,考虑串结构的特殊性,使每个结点存放若干个字符,这种结构称为块链结构。
2. 串的模式匹配 / \(KMP\) 算法
1. 串的匹配
- 目标串:主串
- 模式串:子串
- 匹配:在目标串当中找到子串的位置
2. \(KMP\) 算法
-
算法出发点:利用前面已经匹配的结果,进行 无回溯 的匹配
-
next[]
表示将模式串向右滑动尽可能远的一段距离 -
next[]
的本质:找到模式串中 最长的相同前缀和后缀 -
算法:
- 计算
next[]
数组
/* *next的定义 * next[j] = -1, when j = 0; * next[j] = max{相同的前缀与后缀的长度} * next[j] = 0, otherwise(即没有匹配到) */ void build_next(vector<int>& next, string str){ next[0] = -1; int i = 0 , j = -1; //j = -1,i and j both ++; while(i < str.length() - 1){ if(j == -1 || str[i] == str[j]) { next[++i] = ++j; } else j = next[j]; //can not match, j goes back } }
- 匹配
int strStr(string target_string, string pattern_string) { int n = target_string.length(); int m = pattern_string.length(); int i = 0 , j = 0; vector<int> next(m); build_next(next , pattern_string); //get next[] while(i < n && j < m){ if(j == -1 || target_string[i] == pattern_string[j]){ ++i ,++j; } else j = next[j]; } if(j == m) return i - j; //j == m, 匹配成功 else return -1; // fail to match }
- 计算
-
改进的 \(KMP\) 算法
- 对于下面这种情况:有多个相同的连续字符,显然如果匹配不成功可以直接跳过这一大段连续的相同字符,因此对于新的
nextval[]
,我们有- 如果当前模式串位置的字符和目标串位置的字符 不相同,那么
nextval[index] = next[index]
- 如果当前模式串位置的字符和目标串位置的字符 相同,那么
nextval[index] = nextval[next[index]]
- 如果当前模式串位置的字符和目标串位置的字符 不相同,那么
- 例子
index 0 1 2 3 4 5 6 7 8 9 10 11 12 pattern a a a b b a b c c a a a a next
-1 0 1 2 0 0 1 0 0 0 1 2 3 nextval
-1 -1 -1 2 0 -1 1 0 0 -1 -1 -1 3 - 算法
void build_nextval(vector<int>& nextval, string str){ nextval[0] = -1; int i = 0 , j = -1; while(i < str.length() - 1){ if(j == -1 || str[i] == str[j]) { ++i , ++j; /*nextval[index] = next[index]*/ if(str[i] != str[j]) nextval[i] = j; /*nextval[index] = nextval[next[index]]*/ else nextval[i] = nextval[j]; } else j = nextval[j]; } }
- 对于下面这种情况:有多个相同的连续字符,显然如果匹配不成功可以直接跳过这一大段连续的相同字符,因此对于新的