学习笔记

字符串匹配

主串和模式串

在字符串A中寻找字符串B，则A为主串，B为模式串，记主串长度为N，模式串长度为M

暴力匹配(BF算法-brute force)

在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的，时间复杂度为O(M*N)，绝大多数情况下，此算法性能足够。

RK算法(Rabin-Karp算法)

通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。时间复杂度为O(n)，哈希结果大量冲突的时候，会退化为O(N*M).

KMP算法(Knuth Morris Pratt 算法)

假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。