我的 Obsidian 知识库

第4章 串

17分钟阅读

4.1 串的定义和实现

4.1.1 串的定义

串的定义和基本操作.pdf

  • 串: 即字符串，零个或多个字符组成的有限序列，如 S = 'iPhone 11 Pro Max?'；

  • 串名：S是串名，单引号括起来的字符序列是串的值（有些地方用双引号）

  • 串的长度：串中字符的个数 ， 时的串称为空串

  • 子串：串中任意多个连续的字符组成的子序列称为该串的子串，空串也是该串的子串

    主串：包含子串的串；

  • 字符在主串中的位置：某个字符在串中的序号（从1开始）；

    子串在主串中的位置：子串的第一个字符在主串中的位置；

  • 空串 V.S 空格串：

    • M = '' 是空串；

    • N = ' ' 是空格串；

  • 串 V.S 线性表：

    • 串是特殊的线性表，数据元素之间呈线性关系（逻辑结构相似）；

    • 串的数据对象限定为字符集：中文字符、英文字符、数字字符、标点字符…

    • 串的基本操作，如增删改除通常以子串为操作对象

4.1.2 串的基本操作

假设有串 T = ''，S = 'iPhone 11 Pro Max?'，W = 'Pro'

  • StrAssign(&T, chars)：赋值操作，把串 T 赋值为 chars；

  • StrCopy(&T, S)：复制操作，把串 S复制得到串T；

  • StrEmpty(S)：判空操作，若 S 为空串，则返回 TRUE，否则返回 False；

  • StrLength(S)：求串长，返回串 S 的元素个数；即：返回length值

  • ClearString(&S)：清空操作，将 S 清为空串；即：将 length = 0，逻辑上清空，但是内存中还有

  • DestroyString(&S)：销毁串，将串 S 销毁——回收存储空间；

  • Concat(&T, S1, S2)：串联联接，用 T 返回由 S1 和 S2 联接而成的新串———可能会导致存储空间的扩展。如：执行Concat(&T, S, W)后，T = ‘iPhone 11 Pro Max?Pro’

  • SubString(&Sub, S, pos, len)：求子串，用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串；

    如：执行SubString(&T, S, 4, 6)后，T = ‘one 11’

  • Index(S, T)：定位操作，若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置，否则返回 0 。如：执行Index(S, T)后，返回11

  • StrCompare(S, T)：串的比较操作，参照英文词典排序方式，从第一个字符开始往后依次对比，先出现更大字符的串就更大；长串前缀与短串相同时，长串更大。 若 S > T，返回值>0；S = T，返回值=0 (需要两个串完全相同) ；S < T，返回值<0；

拓展：字符集编码

  • 字符集：英文字符——ASCII字符集，中英文——Unicode字符集。基于同一个字符集，可以有多种编码方案，如：UTF-8，UTF-16，不同字符所占空间不同

  • 编码方案：ASCII编码

  • 乱码问题->解码方式出现错误

4.1.3 串的存储结构

串的存储结构.pdf

串的顺序存储

#define MAXLEN 255   //预定义最大串长为255
 
typedef struct{
	char ch[MAXLEN];   //静态数组实现（定长顺序存储）
		//每个分量存储一个字符
		//每个char字符占1B
	int length;        //串的实际长度
}SString;

串长的两种表示法：

  • 方案一：用一个额外的变量length来存放串的长度（保留ch[0]）；

  • 方案二：用ch[0]充当length；

    • 优点：字符的位序和数组下标相同

    • 缺点：字符串长度不能超过255

  • 方案三：没有length变量，以字符'\0'表示结尾（对应ASCII码的0000 0000）；

    • 缺点：需要从头到尾遍历

  • 方案四：（最终使用方案）ch[0]废弃不用，声明int型变量length来存放串的长度（方案一与方案二的结合）

\begin{document}
	\begin{tikzpicture}[scale=1,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\foreach \char [count=\i] in {H,e,l,l,o, ,w,o,r,d,!, , , , , } {
			\node[fill=gray!20] at (\i-1,4) {\char};
		}
		\node[fill=green!20] at(16,4){11};
 
		\foreach \char [count=\i] in {H,e,l,l,o, ,w,o,r,d,!, , , , } {
			\node[fill=gray!20] at (\i,3) {\char};
		}
		\node at(0,3) {11};
 
		\foreach \char [count=\i] in {H,e,l,l,o, ,w,o,r,d,!, , , , , } {
			\node[fill=gray!20] at (\i-1,2) {\char};
		}
		\node at(11,2) {\textbackslash 0};
 
		\foreach \char [count=\i] in {H,e,l,l,o, ,w,o,r,d,!, , , , } {
			\node[fill=gray!20] at (\i,1) {\char};
		}
		\node at(0,1) {};
		\node[fill=green!20] at(16,1){11};
	\end{tikzpicture}
\end{document}

堆分配存储表示（动态数组）

//动态数组实现
typedef struct{
	char *ch;		//按串长分配存储区，ch指向串的基地址
	int length;		//串的长度
}HString;
 
HString S;
S.ch = (char *) malloc(MAXLINE * sizeof(char)); //基地址指针指向连续空间的起始位置
//malloc()需要手动free()
S.length;

基本操作实现

基于方案四

#define MAXLEN 255
 
typedef struct{
	char ch[MAXLEN];
	int length;
}SString;

求子串

bool SubString(SString &Sub, SString S, int pos, int len){
	if (pos+len-1 > S.length)	 //防止子串范围越界
		return false;
	for (int i=pos; i<pos+len; i++)
		Sub.ch[i-pos+1] = S.ch[i];
	Sub.length = len;
	return true;
}

比较两个串的大小

int StrCompare(SString S, SString T){
	for (int i; i<S.length && i<T.length; i++){
		if(S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
	}
	//扫描过的所有字符都相同，则长度长的串更大
	return S.length - T.length;
}

定位操作：取子串，判断是否相等

//个人理解：从前往后不断取子串，并判断取到的子串与所给子串是否相等
int Index(SString S, SString T){
	int i=1, n = StrLength(S), m = StrLength(T);
	SString sub;		//用于暂存子串
 
	while(i <= n-m+1){
		SubString(Sub,S,i,m);
		if(StrCompare(Sub,T)!=0)
			++i;
		else
			return i;	// 返回子串在主串中的位置
	}
	return 0;			//S中不存在与T相等的子串
}

注：结合顺序表思考优缺点

串的链式存储

typedef struct StringNode{
	char ch;           //每个结点存1个字符
	struct StringNode *next;
}StringNode, * String;

  • 问题：存储密度低，每个字符1B，每个指针4B；

  • 解决方案：每一个链表的结点存储多个字符——每个结点称为块——块链结构

    末尾可用一些特殊字符（如‘\0’来填充）

typedef struct StringNode{
	char ch[4];           //每个结点存多个字符
	struct StringNode *next;
}StringNode, * String;

注：结合链表思考优缺点

  • 存储分配角度：链式存储的字符串无需占用连续空间，存储空间分配更灵活；

  • 操作角度：若要在字符串中插入或删除某些字符，则顺序存储方式需要移动大量字符，而链式存储不用；

  • 若要按位序查找字符，则顺序存储支持随机访问，而链式存储只支持顺序访问；

4.2 串的模式匹配

LeetCode28. 找出字符串中第一个匹配项的下标

  • 什么是字符串的模式匹配？

    • 子串：主串的一部分，一定存在

    • 模式串：不一定能在主串中找到

    • 字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置

4.2.1 朴素模式匹配算法

朴素模式匹配算法.pdf

暴力解法，找到所有可能的子串，把这些这串模式串一一对比，即 Index(S, T)

//个人理解：将主串中所有与模式串长度相同的子串依次与模式串对比，直到找到一个完全匹配的子串或者所有的子串都不匹配为止
int Index(SString S, SString T){
	int i=1;		//主串上的指针，扫描主串S
	int j=1;		//模式串上的指针，扫描模式串T
	while(i<=S.length && j<=T.length){
		if(S.ch[i] == T.ch[j]){
			++i;
			++j;	//继续比较后继字符
		} else{
			i = i-j+2;	//主串指针 i 指向下一个子串的第一个位置【注意】
			//主串和模式串上的指针在if(true)内的循环一共后移了(j-1)个位置（从j=1开始算）
			//主串指针i需要回到相对于这轮刚开始指针i位置的下一个，故+1
			j = 1;		//模式串指针 j 回到模式串的起始位置
		}
	}
	if(j>T.length)			//子串匹配成功
		return i-T.length;	//返回子串第一个位置
	else
		return 0;
}

时间复杂度分析：

  • 主串长度为 ，模式串长度为 ，最多比较 个子串

  • 最坏时间复杂度

    • 每个子串都要对比 个字符（对比到最后一个字符才匹配不上），共要对比 个子串，复杂度 =

    • 注：大多数时候，

  • 最好时间复杂度

    • 每个子串的第一个字符就匹配失败，共要对比 个子串，复杂度 =

4.2.2 改进的模式匹配算法——KMP算法

KMP算法.pdf

  • 在子串与模式串不匹配的字符之前，前面的字符一定是和模式串一致的，这些字符是已知的

  • 根据模式串 T，求出 next 数组（只与模式串有关，与主串无关），利用 next 数组进行匹配，当匹配失败时，主串的指针 i 不再回溯！

  • 即在子串的第 j 个字符与主串发生失配时，跳到子串的next[j]位置重新与主串当前位置进行比较

当第一个元素匹配失败时，匹配下一个相邻子串，令j=0, i++, j++

第4章 串-KMP算法.drawio

预处理求 next 数组

会手算即可

求next数组.pdf

  • 作用：记录 j，当模式串的第 j 个字符与主串的第 i 个字符匹配失败时，使用模式串的第next[j]个元素与主串的第 i 个字符继续匹配；

  • 对于任何模式串，当第1个字符不匹配时，只能匹配下一个子串，因此，next[1] = 0——表示模式串应右移一位，主串当前指针后移一位，再和模式串的第1字符进行比较；

  • 对于任何模式串，当第2个字符不匹配时，应尝试匹配模式串的第一个字符，因此，next[2] = 1；

  • 手算：在不匹配的位置前边，画一条分界线，分界线右边为 S[i] 和 T[j] ，将模式串一步步后退，直到分界线之前能对上，或者模式串完全跨过分界线，此时 j 指向哪儿，next 数组就是多少

例：对于串 T = 'abaabc'

编号123456
next[j]0（通用）1（通用）1223

关键点

  • 假设模式串的第 个字符与主串中的第 个字符发生失配，则前 个字符与主串相同，所以提前把前模式串的 个字符进行对比

  • 对比过后，移动到图示位置继续匹配主串当中的第 个元素

  • next[j] 表示模式串的第 个元素失配后，使用模式串的第 next[j] 个元素继续与当中的第 个元素匹配

第4章 串-KMP算法求next数组.drawio

利用 next 数组进行模式匹配

//个人理解：有了next数组，主串S上的指针就不需要回溯，但需要主串上的失配字符和模式串T上next数组对应的元素再次匹配
 
int Index_KMP(SString S, SString T, int next[]){
	int i=1;	//主串上的指针，扫描主串S
	int j=1;	//模式串上的指针，扫描模式串T
	while（i<S.length && j<=T.length){
		if(j==0 || S.ch[i]==T.ch[j]){
		//当第一个元素不匹配时，直接右移，下次还将匹配第一个元素。
		//next[j]=0, 利用j++来让模式串右移1位
			++j;
			++i;	//继续比较后继字符
		} else			//主串指针i不需要回溯
			j=next[j]	//模式串根据next数组向右移动
	}
	if(j>T.length)
		return i-T.length; //匹配成功
	else
		return 0;
}

时间复杂度分析：

  • 求 next 数组时间复杂度 =

  • 模式匹配过程最坏时间复杂度 =

  • KMP算法的最坏时间复杂度 =

4.2.3 KMP算法的进一步优化

对next数组进一步优化

KMP算法的进一步优化.pdf

  • 判断next数组所指的字符ch[next[j]]与原本失配的字符ch[j]是否相等：

    • 如果不相等，就保持原有状态；

    • 如果相等，则没必要再次地比较，可以直接令j=next[next[j]]

  • 手算求nextval数组

    1. 求 next 数组

    2. 若ch[next[j]]=ch[j]，则令 nextval[j] = nextval[next[j]]

//个人理解：如果next数组所指的元素和失配元素相同的话，那么nextval[j] = nextval[next[j]]，可以少匹配几次
 
nextval[1]=0;
for (int j=2; j<=T.length; j++){
	if(T.ch[ next[j] ]==T.ch[j])
		nextval[j] = nextval[ next[j] ];
	else
		nextval[j] = next[j];
}

例：对于串 T = 'aaaab'

序号 j12345
模式串aaaab
next[j]01234
nextval[j]00004
//个人理解：next数组中，主串S上的指针不需要回溯，但需要主串上的失配字符和模式串T上next数组对应的元素再次匹配
//如果next数组对应的元素和模式串上的失配字符相同的话，再次匹配注定会失败，所以直接把nextval数组的值改成这个相同元素的nextval数组的值，从而减少匹配次数，代码上除了数组不同外几乎没有区别
 
 
int Index_KMP(SString S, SString T, int nextval[]){
	int i=1;	//主串上的指针，扫描主串S
	int j=1;	//模式串上的指针，扫描模式串T
	while（i<S.length && j<=T.length){
		if(j==0 || S.ch[i]==T.ch[j]){	//j==0是为了让第一个字符失配时，模式串右移1位
			++j;
			++i;	//继续比较后继字符
		}
		else
						//主串指针i不需要回溯
			j=nextval[j]	//模式串根据nextval数组向右移动
	}
	if(j>T.length)
		return i-T.length;	//匹配成功
	else
		return 0;
}

4.2.4 本节习题精选

选择题：题目、解析

综合题：题目、解析

关系图谱

反向链接