字符串匹配问题的几种解法：暴力、正则表达式、RK、KMP

字符串匹配算法，是在实际工程中经常遇到的问题，也是笔试面试的常考题目。此算法通常输入为原字符串（string）和子串（pattern），要求返回子串在原字符串中首次出现的位置。

参考博文：https://www.cnblogs.com/phinza/p/11751114.html

图片说明
图中字符串B是A的连续子序列，B第一次在A中出现的位置下标是2，所以返回 2

方法一：暴力检索 / BF(Brute Force)算法
图片说明
优点：简单粗暴；缺点：效率低下

设主串长度为m，模式串长度为n，最坏情况下时间复杂度为O(mn)，如下图
图片说明

方法二：正则表达式 (Regular expression)

使用python的re模块查找所有匹配元素的下标：
finditer函数返回匹配的字符串下标，用findall返回匹配的字符串
import re
s='abababcedgf'
f=re.finditer('bc',s)
for i in f:
res=i.span()
print(res[0])
输出：5

针对字符串匹配问题的变体：连续子序列
方法三：RK算法 / 哈希检索
Q：给定一个字符串 S 和一个字符串 T，计算在 S 的连续子序列中 T 出现的个数
A：在BF算法中，每一个字符都需要进行比较，并且当首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中只进行一次比较就可以判定两者是否相等。
图片说明
首先计算子串的HASH值，之后分别取原字符串中子串长度的字符串计算HASH值，比较两者是否相等：如果HASH值不同，则两者必定不匹配；如果相同，由于哈希冲突存在，也需要按照BF算法再次判定。

而关于哈希算法的设计就非常有技巧了。我们假设要匹配的字符串的字符集中只包含K个字符，通常用一个K进制数据来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值。
比如要处理的字符串只包含 a-z 这26个小写字母，那我们就用二十六进制表表示一个字符串。我们把 a-z 这26个字符映射到 0-25这26个数字，a就表示0，b就表示1，以此类推，z表示25。
在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含a到z这26个字符的字符串，计算哈希的时候，我们只需要把进位从10改成26就可以。

方法四：KMP算法 / 动态规划
首先理解一个概念：部分匹配表PML(Partial match list)——“前缀”和“后缀”的最长的共有元素的长度。

以“ABCDABD”为例：
"A"的前缀和后缀都为空集，共有元素的长度为0；
"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

图片说明
首先，左端对齐，比较第一个字符，如果不相等，子串向后移动，直到子串的第一个字符能和原字符串匹配。

当D与‘ ’匹配失败时，BF算法是将子串整体向后移动一位接着从头比较；但KMP算法的思想是既然已经比较过了“ABCDAB”，就要利用这个信息。
刚才已经匹配的位数为6，最后一个匹配的字符为“B”， “B”对应的部分匹配值为2，那么移动的位数按照如下公式计算：
公式：移动位数 = 已匹配的位数 - 最后一个匹配字符的部分匹配值
6 - 2 = 4，子串向后移动4位
图片说明

“部分匹配”的本质是，有时候，字符串头部和尾部会有重复。比如，“ABCDAB”之中有两个“AB”，那么它的“部分匹配值”就是2（“AB”的长度）。搜索词移动的时候，第一个“AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个“AB”的位置。

在计算“部分匹配表”时，一般使用动态规划算法来实现。
DP[i]的值实际上与DP[i-1]的值有关联，匹配时可能出现下面几种情况：
1.如果DP[i-1]存在值，说明与前面的字符串前缀已经开始匹配了
1.1 如果对应字符s[i]等于下一个应该轮到匹配的前面的字符，则最长共有元素的长度继续增加一个单位
如：将ABCAB 中的第二个B与第一个B进行匹配。
则DP[i] = DP[i-1]+1 【情况一】
1.2 如果对应字符s[i]不等于下一个应该轮到匹配的前面的字符，此时又有两个情况分支：
① 如果s[i]等于字符串的第一个字符，则又可以在此开始新的一轮匹配，
如：ABCAA，在这里第三个A不等于B，但是它等于第一个A，所以DP[i]仍为1 【情况二】
② 如果s[i]不等于字符串的第一个字符，那DP[i]就为0 【情况三】
如：ABCAC，第二个C的部分匹配值就为0
2. 如果DP[i-1]不存在值，说明之前一个单位也没有匹配的情况，
如果对应字符s[i]等于字符串第一个字符，则DP[i] = 1，在此开始新的匹配【情况四】
如果对应字符s[i]不等于字符串第一个字符，则DP[i] = 0 【情况五】

总结一下，【情况二三】和【情况四五】其实可以放在一起讨论：
把【情况一】的实现条件整合一下：
条件一：DP[i-1]存在值
条件二：s[i] 等于轮到匹配的前面的字符
实现上述两个条件则DP[i] = DP[i-1]+1
不符合上述条件的直接分类到【情况二三四五】:
如果对应字符s[i]等于字符串第一个字符，则DP[i] = 1，在此开始新的匹配【情况二/四】
如果对应字符s[i]不等于字符串第一个字符，则DP[i] = 0 【情况三/五】