字符串匹配

字符串匹配(模式匹配)的分类

BF算法(brute-force)

主要思想：

从左往右，依次比较，每次移动一个字符位置。比较方向可以任意选定。无预处理阶段。

也就是暴力比较。

时间复杂度为O(n*m)

context = "GCACTGCAGCACAGCAGCAGTACG"
model = "GCAGCAG"

def BP(context, model):
    model_length = len(model)
    context_length = len(context)
    error = 0
    offset = context_length - model_length
    if offset < 0:
        return False
    for i in range(0, offset):
        for j in range(model_length):
            error += 1
            if context[i+j] != model[j]:
                break
            else:
                if j == model_length-1:
                    print("error: ", error)
                    return i
    print("error: ", error)
    return False

result = BP(context, model)
print(result)

KMP算法

kmp算法核心思想：控制回溯尺度(不回溯思想)

如此例子所示，当e和d发生失配的时候，BF算法是将已经匹配的字符全部回溯，从第一个重新开始匹配。

但是kmp则根据最长公共前后缀，此处为前缀ab和后缀ab，会将前缀移动到后缀处，控制了回溯尺度(也就相当于跳的更远了些。

显然关键在于求解next数组

例子：

nextval数组

nextval数组是next数组的修正版，主要解决了模式串中大量连续重复连续的字符，减少了主串的无用比较次数。

BM算法

BM算法是另一种能够充分利用模式串特征，尽可能排除多的无效字符匹配的单模式匹配算法。

主要思想：

算法从正文左端开始于模式串对其并向右扫描，对齐后从模式最右端开始从右向左进行字符匹配。在发生不匹配的时候，用两个预先计算的函数**坏字符(bad character)和好后缀(good suffix)**来确定模式串移动的距离。

坏字符原则

坏字符原则1：模式串中不存在对应的坏字符：直接右移模式串到坏字符右侧。

坏字符原则2：模式串中存在对应的坏字符，找到最右的对应字符。

原则2a：失配位置在该字符右侧时：让模式串右移，使得最右的对应字符与坏字符相对。

原则2b：失配位置在该字符左侧时：模式串右移一步。

（移动过程中，模式串不能相对于文本串走回头路）

但是会出现字符风暴问题：

好后缀原则

好后缀原则1：模式串中有字串和好后缀完全匹配，则将最靠右的那个字串移动到好后缀的位置继续匹配。

注意：bmGs数组在找和好后缀相同的子串的时候，一般还需要往左多看一个字符，确保两个子串前一个字符不同，才算找到相同字串。

好后缀原则2：如果不存在和好后缀完全匹配的字串，但在好后缀中存在某个最长后缀，使得模式的整个前缀与这个后缀匹配，将这个最长后缀与前缀对齐。(和KMP类似)

好后缀原则3：如果完全不存在和好后缀满足以上两个原则的字串，则右移整个模式串。

坏字符数组bmBc数组的构造

好后缀数组bmGs数组的构造

suffix数组：

单模式匹配算法复杂度分析

BP：O(n*m)

KMP：

KMP算法的时间复杂度为O(m+n)，其中m是模式串的长度，n是文本串的长度。

具体来说，KMP算法的时间复杂度由两个部分构成：

1. 构造前缀表（也就是next数组）的时间复杂度为O(m)，因为需要对模式串进行前缀匹配。

2. 匹配的时间复杂度为O(n)，因为需要对文本串的每个字符都进行一次匹配操作。

这两个部分的时间复杂度相加即可得到KMP算法的总体时间复杂度为O(m+n)。

BM：

时间复杂度以上BM算法是个初级版本。这个版本，在极端情况下，预处理计算suffix数组、prefix数组的性能会比较差。比如模式串是aaaaaaa这种包含很多重复的字符的模式串，预处理的时间复杂度就是O（m^2）。如何优化这种极端情况下的时间复杂度退化，以后再找空研究。实际上，BM算法的时间复杂度分析起来是非常复杂，论文"A new proof of the linearity of the Boyer-Moore string searching algorithm"证明了在最坏情况下，BM算法的比较次数上限是5n。论文"Tight bounds on the complexity of the Boyer-
Moore string matching algorithm"证明了在最坏情况下，BM算法的比较次数上限是3n。