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