0%

1.串的定义

串: 是由零个或多个字符组成的有序序列,又名叫字符串。
一般地,记为s=“a1a2…an”(n>=0)

串中的字符数目n称为串的长度。
零个字符的串称为空串
空格串,只包含又空格的串。注意它与空串的区别,空格串是有内容有长度的。
子串与主串,串中任意个数的连续字符组成的子序列称为该串的子串,相应的包含子串的串称为主串

2.串的比较

串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。

计算机中常用字符使用的标准是ASCII编码,由7位二进制表示一个字符,总共可以表示128个字符。但是后来发现一些特殊字符的出现,128个不够了。就扩展了ASCII编码,由8位二进制表示一个字符,总共可以表示128个字符,这样就总共可以表示256个字符。但世界上由成千上万种语言,256个字符显然不够,于是就出现了Unicode编码,由16位二进制表示一个字符.为了和ASCII兼容,Unicode的前256个字符与ACSCII码完全相同。

3.串的抽象数据类型

图片来源:《大话数据结构》

4.串的存储结构

串的顺序存储结构:用一组地址连续的存储串中的字符序列。按照预定义的大小,位每个定义的串变量分配一个固定长度的存储区,一般使用定长数组来定义。
对于串的顺序存储结构,有一些变化,串值的存储空间可在程序执行过程中动态分配。比如计算机中由一个自由存储区,叫做“堆”。这个堆由C语言的free()和malloc()来管理。

串的链式存储结构:串的链式存储结构,与线性表相似,但由于结构的特殊性,结构中的每个元素是一个字符,如果简单的应用链表存储串值,那么就会造成很大的空间浪费。因此一个结点可以放一个字符,也可以放多个字符。
当然这里一个结点放多少字符很重要,会直接影响到串处理的效率。

5.朴素的模式匹配算法

子串在主串中的定位操作通常称为串的模式匹配

例如:在主串S=”goodgoogle”中,找到T=”google”这个子串的位置。通常需要下面几个步骤

  1. 从主串的第一位开始,有三个字符相匹配,但第四个字符不相匹配。所以匹配失败。
  2. 接下来从主串第二位字符开始,依次到第四位字符,均匹配失败。
  3. 直到主串第五位字符开始,6个字符均匹配,匹配成功。

假设主串S和要匹配的子串T的长度存在S[0]与T[0]中,实现代码如下:

这种算法的时间复杂度位O(m+n),n为主串的长度,m为子串长度。 这时候有一个最坏情况,例如:主串为:00000000000000000000000000000001,子串位:000000000001,在匹配时,每一次都将T中字符循环到最后一位才发现它们原来不匹配。因此最坏情况的时间复杂度为O((n-m+1)*m). 这在计算机的实际运算中,非常低效。

6.KMP模式匹配算法

例如:主串S=”abcdefgab”,子串T=”abcdex”,如果使用前面的朴素算法的话,前五个字母完全相等,直到第6个字母,”f”与”g”不等。
在我们的观察中T中首字母”a”与后面的串”bcdex”任意一个字母都不相等。那么对于朴素算法的第一步,S的a与T的a匹配时,前五位字符均相等,所以可以省略,T的a与S中的bcde相匹配。

那么当T串后面也包含首字母”a”的字符怎么办?
例如:主串S=”abcabcabc”,T=”abcabx”,对于开始的判断,前五个字母相等,第6个字符不相等。
根据刚才的经验,T的首字符a与S的第2个字符b、第3个字符c均不等,所以不需要进行判断。

综上,我们在朴素的模式匹配算法中,主串的i值是不断回溯的。而根据我们的分析,这种回溯是不需要的,而我们的KMP模式匹配算法也正是让这不必要的回溯不发生。
既然i值不回溯,也就是不变小,那要考虑的变化就是j值了。
我们把j值的变化定义为一个数组next,那么next的长度就是T串的长度。于是我们可以得到下面的函数定义。

## next数组值推导 1.

3.

KMP模式匹配算法实现

计算要匹配的串T的next数组

通过得到的next数组进行KMP模式匹配算法

加粗部分为相对于朴素算法增加的代码,改动不大,关键是去除了i值回溯的部分。该算法的时间复杂度为O(m+n)

KMP模式匹配算法改进

后来有人发现,KMP还是有缺陷的。比如,我们的主串S=”aaaabcde”子串T=”aaaaax”,其next数组值为012345,由于T串的第二、三、四、五位置的字符都与首位的a都相等。因此可以用首字母next[1]的值去取代与它相等的字符后续next[j]的值。

假设取代的数组位nextval,增加了加粗部分。

nextval数值推导

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!