前言
一切都要从 LeetCode
的第 28 题 实现 strStr()
开始说起,当自己脑子里的第一种暴力查找法写出来并 AC 之后,还是觉得不满足,决定把能找到的解法都理解了,于是便有了这个系列。
字符串匹配的整体思路
当我理解完四种经典的匹配算法之后,总结了一下这类操作的核心:
将
模式串
和主串
进行比较- 从前往后比较
- 从后往前比较
- 匹配时,比较
主串
和模式串
的下一个位置 失配时,
在
模式串
中寻找一个合适的位置* 如果找到,从这个位置开始与`主串`当前失配位置进行比较 * 如果未找到,从`模式串`的头部与`主串`失配位置的下一个位置进行比较
- 在
主串
中找到一个合适的位置,重新与模式串
进行比较
所以总的来说,之所以会有这么多种匹配算法,本质上就是一些大神对第1步和第3步进行了优化,这个核心思路一定要牢牢的先记在脑子里,这样之后理解优化的匹配算法就不会一脸懵逼。
算法介绍与分析
介绍
BF 算法,Brute-Force(暴力)法的简称,完全没有优化,每次失配时从主串
的下一个位置进行比较,直到比较结束。
分析
算法描述如下:
- 将
模式串
和主串
从前往后比较 - 匹配时,比较
主串
和模式串
的下一个位置 - 失配时,从
主串
的下一个位置开始与模式串
的头部重新开始比较
我们假设有 主串 ABABBBAAABABABBA 和 模式串 ABABABB ,
下面放五张图来理解一下这个过程:
上面这两幅图,表现的是第1步和第2步,可以看出:
- 从
S[0]
和P[0]
开始从头往后比较 - 如果匹配,比较
S[i++]
和S[j++]
上面这两幅图,则表现的时第3步,可以看出:
- 如果
S[i]
和P[j]
失配 j = 0
从P[0]
也就是模式串
头部开始与主串
的下一个位置S[i - (j - 1)]
开始继续进行匹配
重复上述两步,直到下图完全匹配或者找不到模式串为止
代码
思路还是很好理解的,但是代码怎么写呢?
其实我一直觉得刷 LeetCode
除了巩固与提高数据结构与算法的能力之外,最重要的就是训练一种把思路翻译成代码的能力,下面我来尝试翻译一下上述的算法思路。
1、先进行极端情况的排除
这个操作应该是刷题刷多了,像以前做数学题写“解”的操作
2、写出整体的结构
- 从算法的思路很容易看出,这里的“重复上诉两步”,明显是要翻译成循环操作
如果是循环,那么终止条件是什么,可以很快想到,只有两种终止情况:
主串
中没有找到模式串
的匹配,此时i = haystack.length
主串
中找到了模式串
的匹配,此时j = needle.length
算法处理过程主要是两步,所以这里一定有一个分支结构
- 匹配
- 失配
- 如果没找到,直接
return -1
就好了,但要是找到了,应该怎么确定那个index
的值呢?根据上面成功的图,我们可以发现,匹配的位置8
,是等于主串
的末尾14
减去模式串
的末尾6
得到的,也就是最后匹配的那个index = i - j
3、补充具体操作
根据算法分析里的描述,很容易知道
- 匹配,
i++; j++;
比较各自的下一位 - 失配,
i = i - (j - 1); j = 0;
重新进行下一轮匹配
总结
至此,整个BF算法的分析与编写就完成了,虽然它是一个毫无优化的结构,但是体现出了所有字符串匹配算法的基本思想,计算机不是人,可以通过眼睛观察和大脑思考来进行定位,它只能通过一个一个字符的比较来进行判定,接下来的算法,就开始运用到一些骚操作来进行优化这个匹配的过程。
后记
“字符串匹配算法”是“重学数据结构与算法”系列笔记中的一个章节,细分为以下几个部分,之后会陆续填坑。
- 字符串匹配算法(一)——BF算法
- [字符串匹配算法(二)——KMP算法]()
- [字符串匹配算法(三)——BM算法]()
- [字符串匹配算法(四)——Sunday算法]()