EraGuide

# 串

# 一、概念

串是由零个或多个字符组成的有序序列，一般记为

串与线性表异同

  • 串从逻辑上和线性表类似，串是限定了元素为字符的线性表
  • 从操作集上，线性表的操作主要针对表内的某个元素而出，而串的操作主要针对串内的一个子串
  • 串值：是可以直接引用的串，如“strand",一般用单引号或双引号作为分界符，引号不属于串的内容
  • 串长：串中所包含字符个数称为串的长度
  • 空串：长度为零的串称为空串，它不包含任何字符
  • 空格串：构成串的所有字符都是空格的串称为空格串
  • 子串：串中任意个连续字符组成的子序列称为该串的子串。空串是任意串的子串，任意串是其自身的子串，包含子串的串相应的称为主串
  • 串相等：如果两个串的串值相等，即两个串的长度和各个对应位置的字符都相同时，这两个串相等

# 二、串的存储

串是一种特殊的线性表，其存储表示和线性表类似。串主要介绍三种机内表示方式：

# 1.定长顺序存储

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列，其大小不能改变。

#define MAXSIZE 100
typedef struct{
	char ch[MAXSIZE];
	int length;
}SString;
1
2
3
4
5

# 2.堆分配存储

用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序执行时动态分配的。

typedef struct{
	char *ch;
	int length;
}HString;
1
2
3
4

# 3.块链存储表示

链式存储结构表示，链表每个元素只有一个字符，但是在具体存储实现时，每个结点既可以存放一个字符，也可以存放多个字符，每个结点称为块，由块组成的链表即块链结构。

image-20221122222359175

# 三、串的模式匹配

子串在主串中的定位称为模式匹配或串匹配。模式匹配成功指的是在主串S中能够找到模式串T，否则称模式串T在主串S中不存在。

# 1.简单模式匹配算法

思想：分别用i和j指针指向主串S和模式串T中的正在比较的字符位置，从主串S指定字符开始（一般为第一个）和模式串T的第一个字符比较，若相等，则继续逐个比较后续字符，直到T中的每个字符依次和S中的一个连续字符序列相等，则称匹配成功；如果比较过程中某对字符不相等，则从主串S的下一个字符起再重新和T的第一个字符比较。如果主串S的字符都比完了仍然没有匹配成功，则称为匹配不成功

image-20221122223947729

int Index(SString S,SString T){
	int i=1,j=1;
	while(i<=S.length && j<=T.length){
		if(S.ch[i] == T.ch[j]){
			++i;++j;
		}else{
			i=i-j+2;j=1;
		}
	}
	if(j>T.length){
		return i-T.length;
	}else{
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 简单模式匹配算法最坏时间复杂度为，其中n和m分别为主串和模式串的长度

# 2.KMP匹配

# 演示

这个算法不容易理解，我们举个例子解释下，假设

主串：BBCABCDABABCDABCDABDF

模式串：ABCDABD

image-20221202171353495

首先，模式串的第一个字符与主串第一个字符进行比较，不匹配，所以主串后移一位

image-20221202171510325

依旧不相等，继续向后搜索

image-20221202171615940

直到这时，主串和模式串第一位已经匹配，同时向后移动比较下一位

image-20221202171715070

后续依旧匹配，继续移动

image-20221202171804003

直到匹配到模式串最后一位时，发现不相等，这不是我们希望找的子串

image-20221202171937257

如果按照"简单模式匹配算法"的思想，此时需要把主串重新移动到起始位置的后一位，从头开始与模式串第一位比较，这样做可行，但是没办法利用已经匹配过的信息，因为我们此时已经知道模式串的前六个字符是ABCDAB，如何利用这个信息使主串不回溯呢

image-20221202172700413

这里我们可以通过模式串得出它的部分匹配值，算出一张部分匹配表，具体怎么算的后边说，先会用就好

TIP

这里记住一个公式：右移位数 = 已匹配的字符数 - 对应的部分匹配值

当最后一个字符A与D不匹配时，前面有六个字符ABCDAB是已经匹配完的，查表可知，最后一个字符B对应的部分匹配值为2，所以右移位数为6 - 2 = 4位

image-20221202172851643

移动到如图位置，这时C与A又发生了不匹配，右移位数 = 2 - 0 = 2，主串再右移两位

image-20221202173535749

逐位比较

image-20221202173636575

直到发现C与D不匹配，于是移动位数 = 6 - 2 = 4，继续移动4位

image-20221202173714171

逐位比较，这时直到模式串最后一位，完全匹配，于是整个搜索完成

# 部分匹配表

这里了解几个概念：前缀、后缀和部分匹配值

  • 前缀：指除最后一个字符外，字符串的所有头部子串
  • 后缀：指除第一个字符外，字符串所有尾部子串
  • 部分匹配值：字符串的前缀和后缀的最长的前后缀长度

下面以'ababa'为例说明

image-20221202174951992

最长相等前后缀长度为3，同理也可算出a,ab,aba,abab的最长前后缀长度分别为0，0，1，2

所以字符串'ababa'的部分匹配值为0 0 1 2 3

最后，再来计算下上面演示部分的部分匹配表

image-20221202172700413

'A':前后缀都为空集，最长相等前后缀长度为0；
'AB':前缀[A],后缀[B]，最长相等前后缀长度为0；
'ABC':前缀[A,AB],后缀[C,BC]，最长相等前后缀长度为0；
'ABCD':前缀[A,AB,ABC],后缀[D,CD,BCD]，最长相等前后缀长度为0；
'ABCDA':前缀[A,AB,ABC,ABCD],后缀[A,DA,CDA,BCDA]，共有[A]，最长相等前后缀长度为1；
'ABCDAB':前缀[A,AB,ABC,ABCD,ABCDA],后缀[B,AB,DAB,CDAB,BCDAB]，共有[AB],最长相等前后缀长度为2；
'ABCDABD':前缀[A,AB,ABC,ABCD,ABCDA,ABCDAB],后缀[D,BD,ABD,DABD,CDABD,BCDABD]，最长相等前后缀长度为0；
所以部分匹配值为0 0 0 0 1 2 0
1
2
3
4
5
6
7
8

部分匹配的实质是有些字符串的头部和尾部有重复部分，移动时就可以从前缀的子串移动到后缀相同的子串以节省匹配时间

数组和广义表 →