算法 036：字符串匹配：模式预处理：朴素算法（Naive)(暴力破解)

算法简介

朴素的字符串匹配算法又称为暴力匹配算法（Brute Force Algorithm），它的主要特点是：

没有预处理阶段；
滑动窗口总是后移 1 位；
对模式中的字符的比较顺序不限定，可以从前到后，也可以从后到前；
匹配阶段需要 O((n - m + 1)m) 的时间复杂度；
需要 2n 次的字符比较。

很显然，朴素的字符串匹配算法 NAIVE-STRING-MATCHER 是最原始的算法，它通过使用循环来检查是否在范围 n-m+1 中存在满足条件 P[1..m] = T[s + 1..s + m] 的有效位移 s。

伪代码如下：

NAIVE-STRING-MATCHER(T, P)
    n <- length[T]
    m <- length[P]
    for s <- 0 to n - m
        do if P[1 .. m] = T[s + 1 .. s + m]
            then print "Pattern occurs with shift" s

对于模式 P = aab 和文本 T = acaabc，将模式 P 沿着 T 从左到右滑动，逐个比较字符以判断模式 P 在文本 T 中是否存在（原文图片丢失，据文字重绘滑动过程）：

s = 0:  a c a a b c
        a a b          失配（P[2]=a 与 T[2]=c 不匹配），滑动窗口后移 1 位
s = 1:  a c a a b c
          a a b        失配（P[1]=a 与 T[2]=c 不匹配），后移 1 位
s = 2:  a c a a b c
            a a b      失配（P[3]=b 与 T[4]=a 不匹配），后移 1 位
s = 3:  a c a a b c
              a a b    匹配成功，有效位移 s = 3

可以看出，NAIVE-STRING-MATCHER 没有对模式 P 进行预处理，所以预处理的时间为 0。而匹配的时间在最坏情况下为 Θ((n-m+1)m)，如果 m = [n/2]，则为 Θ(n²)。

图例分析

假设有两个字符串：

M = "abcdefabcdx"
T = "abcdx"

想要找到 T 串在 M 串中的位置，要怎么找呢？

也就是说，从主串 M 的第一个字符开始分别与子串从开头进行比较，当发现不匹配时，主串回到这一轮开始的下一个字符，子串从头开始比较。直到子串所有的字符都匹配，返回所在主串中的下标。

算法复杂度

假设 S 的长度是 m，T 的长度是 n，暂不考虑 pos，从字符串 S 的开头开始比较。

最好的情况是第一次就匹配了，需要比较的次数是 n。

最坏的情况下，就是上面举的这种例子，需要把整个字符串都比较完，从代码中就体现为把两层循环都跑了一遍。这时候，比较的次数就是 t*(s-t+1)。

所以这个算法的（最坏）时间复杂度就是 o(t(s-t+1))，近似为 o(n²)。

参考文章

系列导航

上一篇：字符串匹配：Overview
下一篇：字符串匹配：KMP 算法
相关篇：字符串匹配：BM 算法 (Boyer-Moore)（三者对比：朴素算法无预处理，KMP 与 BM 均对模式串做预处理）

CHARLIE SAYS