暴力马拉车(BF)的时代结束了,来看看KMP算法吧,简单易用方便快捷!
直接上码
废话不多说,直接上代码
1.动态规划|有限状态自动机
1 | class KMP { |
2.动态规划|空间最优
1 | class KMP { |
优劣
两段代码都非常的容易理解:
代码1是正向思考,枚举在字符串匹配中可能遇到的所有情况,将这些情况的状态变化记录成DP数组,在查找的时候直接无脑代入DP数组就好了,代码看起来繁复的部分基本是由于开二维数组造成的。
代码2是递推思考,思考如果在匹配pattern[n]
的时候如果匹配不上就往前推进到前一个前缀字符串相同的位置,直到匹配成功或者彻底失败,然后重新匹配。
很明显,代码1是空间换时间的做法,如果需要匹配的对象有明确的范围的话(例如为ASCII范围内)且需要匹配的pattern
串长度合适或者需要多次使用,代码1明显更合适。
而代码2中规中矩,基本是KMP最基本的思路,相对可用范围也更宽泛一些,但是在面对重复多次的恶意数据仍然有超时风险。
结论就是:DP党无脑冲1,CPC日常写2(2的码量更小)
讲解
想要看懂KMP,最关键的是要能明白KMP为什么能这么干,也就是KMP的理论依据:
如果text[a:b]匹配pattern[c:d]
那么显然对于pattern[c:d]中的任何pattern[x:d]都有text[y:b]与之对应
如果存在pattern[c:z]与pattern[x:d]相同
那么显然text[y:b]与pattern[c:z]匹配
推理过程如上,稍作理解一下即可,简单来说就是如果已知两段字符串匹配,那么更短相同前缀的模式字符串显然也在同一个位置完全匹配。
如果pattern[j]
与当前的text[i]
并不匹配,那我们就可以尝试去查询pattern
中出现的更短相同前缀的位置,来寻找是否有可以匹配的字符,这样就可以规避大量无意义的繁复“马拉车”。
这也是KMP算法的精髓所在——头可断血可流,字符串绝对不回推。
为了更好的装逼解释这个过程,我们引入动态规划状态
的概念,对于一个长度为$N$的pattern串,认为这个串并不是线性的,而是有$N$个状态分立,处理每个状态时在不同的情况下可能转向不同的状态。
显然当pattern转为第$N+1$个状态时,发生了完整的匹配。
既然如此,状态在不同情况下的转移条件就成为了关键,那么状态转移的条件是什么呢?
代码1和代码2选择了不同的方法描述这个条件:
代码1
代码1选择开辟了一个二维数组
1 | int dp[pat.length()][256]; |
这个数组的功能也很明显,对于每个状态dp[i]
记录当这个状态遇见字符’c’时的转移路径dp[i][c]
核心代码
1 | //必要时需要对dp数组进行初始化 |
理解这个代码的核心在于理解影子状态的存在。
每个状态i
,在遇到pat[i]
的时候转移到顺序状态很好理解,但是其他的情况如何转移呢?
最朴素的思路就是从x=[0:i]依次查找[x:i]是否存在一个最长的字符串与pattern串从0开始完全匹配——等等,匹配?!我们不是正在写用于匹配计算的状态转移数组嘛!
我们是从位置1开始遍历,刚刚好位置0的转移已经写好了,那么如果我们在推进遍历的过程中持续将当前pat[i]
输入状态转移数组,维护一个从位置0开始匹配的X,那么显然X的位置就是最长的更短相同前缀字符串的位置。任意位置i
在遇到任何c!=pat[i]
的时候的处理方式,可以完全参照i状态的影子状态X
的处理方式——既然i状态遇到C无法更进一步到顺序下一个位置,那么就尽可能的前往pattern串中更偏后的位置。
转移数组会在推进的过程中越来越复杂,显然的对于几个具有相同短前缀的位置,后一个位置会通过X继承前一个位置的全部转移方式。
使用这种方法生成dp数组后,在进行查找的时候只需要无脑放心的顺序将text串的每一个字符塞进转移数组就好了,每次判断一下是否抵达完全匹配的状态即可。
代码2
代码2记录转移路径的方法是开辟了一个一维数组
1 | int next[pat.length()]; |
核心代码如下
1 | //next[i]中记录的是状态i+1最近的相同前缀的状态的位置 |
临时兴起改的减缩版
1 | for(int i=1,j=next[0]=0;i<pat.length();next[i++]=pat[i]==pat[j]?++j:j) |
因为对于任何一个状态i只需要考虑前一个更短相同前缀的状态在哪里,原理倒是很好理解,递归查找嘛。
这段代码不好理解的地方主要就是因为太精炼,next数组的意义太绕了。
next[i-1]
记录的是如果状态i匹配失败下一步需要匹配的状态!如果能理解这一点那么这段代码就能完全理解了!