4.1 串在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这章我们讨论串

所谓串是由0个或者多个字符组成的有限序列

一般用来表示需要处理的文本对象

从序列这两个字，大家可以注意到

串本质上就是一个线性表，它是一个序列

它的特殊性体现在它的元素

组成序列的数据元素是一个字符

下面看一下子串的概念

一个字符串当中

任意个连续的字符组成的子序列

称为该串的子串

相应的可以把这个串称为主串

子串在主串中的位置

是以子串的第1个字符在主串的位置来表示的

我们看一下图，图中我们用数组存储了一个串

假设，红色的abcac是它的一个子串

那么这个子串在主串当中的位置

就是以第1个字符a的位置6来表示的

接着我们讨论一下，串和模式匹配

串的模式匹配，也称为子串的定位操作

我们用函数index来实现串的模式匹配

Index中涉及三个参数

其中s称为主串，t称为模式串

Pos给出一个主串中的位置

函数的意思是说，在主串s当中

从pos这个位置开始，寻找是否有和模式串t匹配的子串

串匹配有两个要求，一个是两个串的串长相等

另一个是两个串对应的字符相等

模式匹配算法就是基于这个原理设计的

具体实现我们用图来讲解一下

图①中我们看到，主串s存储在一个数组中

数组0号单元存储该串的串长，串长是13

串的13个字符存在数组的1~13号单元当中

模式串t也用同样的方式存储，模式串t的长度是5

算法是通过多次试探来寻找

是否有长度为5的子串和模式串匹配

假设pos是1，也就是说从主串第1个位置开始试探

第1次试探，就是看一看

从主串中位置1开始到位置5这个子串是否和模式串相等

这里使用了两个指示器，i指示主串的位置

i=1，从主串第1个位置开始试探

j指示模式串的位置，j=1

也从模式串第1个位置开始试探

试探过程中，如果s[i]==t[j]

也就是对应字符相等，则++i；++j

继续考察后续的字符是否相等

这个过程重复进行下去

例子中，这次试探的前两个字符相等

到i=3,j=3的时候，s[i]≠t[j]

说明第1次从位置1开始的试探失败，需要第2次试探

从图②中可以看到，第2次试探

应该是试探从主串位置2开始到位置6

这个子串是否和模式串相等

也就是从上一次试探位置开始的下一个位置

同样取长度为5的子串进行匹配试探

第2次试探的开始位置可以通过i=i-j+2来确定

例子中就是i=3-3+2，i赋值2

2就是第2次试探主串中的开始的位置

模式串仍然是从j=1开始

例子中第2次试探第1个字符就不匹配

马上失败了，那么会开始第3次试探

方法和上面一样

后面的三次试探

就是从345开始的三次试探呢

都是失败的

我们看一下，成功的试探

图③中，这次试探是从i等于6开始

考察6到10这个子串是否和模式串匹配

我们直观的可以看到，这个子串是等于模式串的

一直比较相等，i和j不断自加

直到i=11, j=6，这时候我们注意到j大于6

模式串的长度是5，这说明模式串和子串已经完全匹配了

我们在主串s当中找到了和模式串t匹配的一个字串

这个子串从位置6开始到位置10

此时匹配成功

可以返回和模式串匹配的子串在主串当中的位置了

用return返回i-5，也就是11-5，等于6

这就是子串在主串中的位置

下面我们看一下算法的实现

上述我们讨论的算法称为朴素的模式匹配算法

又叫布鲁特-福斯算法

先看一下串存储结构的定义

我们定义了一个最大的串长是255

定义了一个数组类型的名字sstring

这个数组类型的元素是字符

它的长度是256，主串和模式串都是该类型的变量

在这里，我们约定0号单元不存储字符

而是存储字符串的长度

下面我们看一下算法的实现

Index函数的返回值是一个整形数

当匹配成功的时候

它返回的是模式串在主串当中所匹配子串的第1个字符

在主串当中的位置

匹配失败的时候，返回0

三个参数我们上面介绍过

分别存储主串和模式串

整型参数Pos给出主串中试探开始的位置

首先，i赋值pos，j赋值1

为第1次的试探匹配做好准备

整个试探匹配是黄色这部分

是一个单循环语句

循环条件是i小于等于S[0]

并且j小于等于T[0]

从存储定义中我们知道S[0]和 T[0]中是主串和模式串的长度

从前面匹配成功的例子中，我们可以看到

当j>T[0]的时候，也就是说这次试探j大于了模式串的长度

意味着这次试探匹配是成功的

那么循环就可以结束了。如果试探过程中

i>S[0]意味着主串中找到最后也没有发现和模式串匹配的子串

则模式匹配失败了

循环的过程中就是一个if语句

如果s[i]==t[j]，则++i；++j

继续这一次试探，否则，此次试探失败

我们需要开始下一次的试探

我们把i赋值

i-j+2确定下一次试探主串中的开始位置

模式串总是从第1个位置开始进行试探

循环结束以后，如果有j>T[0]

我们前面已经说过了，这个时候说明匹配成功

我们return i-T[0]

返回匹配子串在主串中的位置

否则，就意味着匹配失败

我们return返回一个0

串的存储和处理在所有的开发平台上都是比较成熟的

所以串的存储以及串上的基本操作的实现

我们就不多加讨论了

好同学们，这一章我们就讲到这儿

下次再见