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

[TOC]

朴素的字符串匹配算法又称为暴力匹配算法(Brute Force Algorithm),最为简单的字符串匹配算法。

1. 算法简介

朴素的字符串匹配算法又称为暴力匹配算法(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 中是否存在。

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

2. 图例分析

假设有两个字符串:

  • M="abcdefabcdx";

  • T="abcdx";

想要找到T串在M串中的位置,要怎么找呢?

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

3. 算法复杂度

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

  • 最好的情况是第一次就匹配了,需要比较的次数是n.

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

所以这个算法的(最坏)时间复杂度就是o(t(s-t+1)),近似为o(n2).

4. 参考文章

  • https://www.cnblogs.com/gaochundong/p/string_matching.html#kmp_string_matching_algorithm

  • https://blog.csdn.net/u013301192/article/details/48507695

  • https://www.pdai.tech/md/algorithm/alg-domain-char-match-bf.html

最后更新于