大家好
数据结构与算法这一讲
我们继续学习第四章
字符串的内容
我们介绍一种朴素的匹配算法
字符串的模式匹配呢
它是在很多应用中
都要进行的一个基本的操作
例如我们在文本编辑器当中
要查找某一个串
然后我删除这个串
或者是说我用另外一个串来替代
要在目标T里面
找到模式P它的一个配串
那就是找到T的某一个下标i开始的
这样连续m个字符
它跟模式P呢
在相应的位置上是相等的
那我们就是说
模式P与目标T是匹配的
我们的目标其实就是
在一个目标串里面呢
找到我们的模式串
它的一个起始的位置
如果是能够合理的找到这个位置
那我们就是匹配成功
如果我们找了一遍还没找到
那就是匹配失败
解决这个模式匹配问题呢
我们主要有两大类算法
第一类就是朴素的算法
其实是一个穷举法
还有一类是无回溯的
快速模式匹配方法
例如KMP的这样的算法
我们来看朴素模式匹配它的例子
我假设这个目标串T
是从t0到tn-1
P是目标串从p0到pm-1
它们的下标分别表示为i和j
如果是匹配成功呢
那就是从这个i开始
我们是p0=ti
然后一直到pm-1
等于ti+m-1
也就是说我们在t里面
从下标i开始
取连续m个字符组成的子串
它是跟我们的模式串
是相等的
如果是匹配失败了
也就是说在这个i位置
连续m个字符
这个子串呢
跟p是不等的
那我们这个时候呢
就把这个目标串呢
就是它的这个i位置呢
再下移一位再继续比较
那我们如果是画一个图来看呢
相当于把这个模式串p呢
右移一下
再跟t的相应的字符
去对齐来比
我们来看朴素匹配的一个例子
我们的模式串是aaaa
一直到最后一个是b
我们的目标串呢
是这么一个形式
发生不等的时候
我们把这个p右移
再跟t对齐了
继续去比
一直比到最后一位呢
它是相等的
那我们匹配成功
再来看第二个例子
我们也是在发生不等的时候呢
p它是右移一位
跟t去对齐再继续比
其实我们观察它这个模式串
它abab这样的一个重复
可以感觉呢
第二趟的比较
它完全是不必要的
下一次的p0和p1
这个位置
它们其实分别是a和b
它是不等的
显然不可能跟t1这个位置相等
所以这里其实是一次冗余的比较
我们再来看一个例子
这个模式串abcdef f
你可以看前面
几乎互相都不相等
但是呢它跟目标串呢
对应的位置
前面基本上相等
只有最后一个不等
不等的情况下
我再去匹配
我还是每次只能把模式
往后面移一位
继续来进行比较
模式串看起来似乎特别没有规律
但是它其实隐含着
一个重要的规律
我们这个p
它相应位的字符
都是不等的
而它跟前面这个模式串t呢
在对应位置上
又是分别对应相等的
我们后面再去比的时候
大家其实可以想像
都是无谓的比较
没有必要
我们已经预先知道
是不可能相等的
但是按照朴素的匹配方法
我只能这样的
一个一个穷举来进行
我们来看朴素匹配方法的实现
首先就是传入的一个目标串s
然后我的模式串是p
在s里面的起始的一个比较位置
是startindex
我首先计算一下s串长减p串长
是等于多少
那这个值呢
就是在s里面
我允许的子串的一个起始位置的
最右边那一个
如果是说这个值
LastIndex它是小于startindex的
那就表示我们不可能找到
合适串长的子串
那我就返回-1
否则我让下标g呢
从startindex开始
然后我一直到Lastindex结束
我对这个g每次加1
进行相应的操作
我是从这个g开始
我取我们这个模式串p
它的串长
这样长度的这么一个子串
我取出来以后
跟这个p进行比较
如果是相等
那我就返回刚才的
这个起始位置g 下标
如果出了这个循环
我们还没有找到
这样的一个合适的g
也就是整个匹配它是失败的
我们返回-1
再来看朴素模式匹配的
第二个算法
其实这个算法跟刚才本质上
是一样的
只是写法不一样
让这个下标i呢
是在目标串里面指定的起始位置
而下标j呢
是模式串里面的0
作为起始位置
当这个i和j
都在合理的字符串范围之内
也就是i小于目标串的长度
j小于模式串的长度
我们再来判断这个相应的
p[j]和t[i]是不是相等
如果相等
那我们让它们分别都加1
然后再继续下一位的比较
如果是不相等
那这个时候呢
我们就让目标串里面这个下标i
返回到刚才我发生这个比较的
那个位置的下一位
模式串里面的下标键
我回到0
出了这个循环
如果j>=p.length()
其实这个地方可以判断
j就是==p.length()
那表示我这个模式串p呢
它已经成功的到达了
这样的一个\0的结束位置
其实也就是在我们的目标串里面
找到了一个配串
那我们就返回i-j
这样的一个起始下标的位置
这个子串就找到了
否则呢如果是出了这个循环
j它小于p.length()
就表示我不能继续再比了
但是这个时候在模式串里面呢
我这个下标j呢
还没有达到尾部
也就是这个匹配是失败的
我们再看一个更简洁一些的写法
它还是一个朴素的
模式匹配算法
我们传入的参数是类似的
我让下标g呢
从你指定的目标串里面的
起始位置开始
当g小于目标串长
减掉我们模式串长
让g逐位进行一个操作
那层循环我让模式串的p
它的下标为j
然后当这个下标j呢
它是小于p.length()
也就是在它的下标范围之内
而且呢这个模式的t里面
起始的g加上j
就是当前这个位置
跟我的模式p的j位置
是相等的时候呢
我就让这个j下标
再++来继续比
如果出了这个内层循环
j它是正好等于
我们模式p的长度
那就表示匹配成功
我可以直接返回
如果是没有等于这个p的长度
而且我这个g呢
它还在合法的
这么一个下标范围内
那我就让g呢
它成为我刚才起始的
那个位置的下一个位置
我再继续这样的一个比较
如果整个出了这个循环
还没有找到合适的起始位置g
那就是匹配失败
返回-1
那我们来看一下
朴素匹配它的算法效率
假设我们目标T
它的长度是n
模式P长度为m
当然m是小于等于n的
最坏情况呢
在外层循环
每一次它都是不成功
可能的起始位置呢
它分别是遍历了从0到n-m的
这样的一个位置
在内层循环呢
就是p和t的相应位置
进行逐位的相比的时候
假设也是比到最后一位
才发现不等
这个内层呢
就会要比m次
那我们合起来呢
就会是大O（m×n）次
这样的操作
我们看一下具体的例子
最坏的情况
目标串是a重复n-1次
最后一个是x这样的字符
模式串是a重复m-1次
最后是字符b
在成功的情况下
我们一直到最后一位
而且x等于b
可以发现我们最外层呢
是要循环n-m+1
然后里层是每次也是要循环m次
总的这个时间复杂度
是O（m×n）
在匹配失败的情况下
假设这个x是c
也是类似的
我们外层要n-m+1次
内层是m次
还是O的m×n次
我们再看朴素模式匹配
最好的情况
在成功的匹配的时候呢
我在前面m个位置
就找到了我的这个模式串
这样的话呢
我就是只需要O（m）
那样多次的查找
就可以找到
在失败的情况下
我每次呢
在这个模式的第一个位置呢
就发生不匹配
因此呢 我内层的循环
只要一次
但是我外层的循环
还是要n-m+1次
我们合起来看呢
它的时间复杂度呢
是O（n）的
最后给大家留一下思考
就是朴素匹配它的算法
它是低效的
正是因为它在里面呢
有一些冗余的比较
我们观察这个例子
就可以看到这些冗余的现象
大家自己再去设计几个例子
你来看一下
这种冗余是为什么出现
我们是不是能够
设计一个更合理的算法
来消除这种冗余
使得我们在进行匹配的时候呢
尽量的让这个目标t
它的下标是不回溯的
也就是说不会一下子
又回到起始点
就是有些中间的这些比较次数呢
我们就可以省略了
谢谢大家