串匹配算法1——蛮力匹配

概述

串匹配问题有很多的算法,我们这里要介绍的蛮力匹配法在应用中一般不会用到,因为它的效率相对后面高级的算法是很低的。但后续高级的算法都可以理解为基于这种蛮力匹配算法的改进和优化,理解它才能更好的学习后续的算法。 我们首先介绍字符串相关的术语和它的基本接口,之后再介绍具体的算法。

术语

  • 相等:长度相等,且每个对应字符都相等
  • 子串:从S[I]起的连续k个字符 S.substr(i, k)
  • 前缀:S中最靠的k个字符 S.prefix(k) = S.substr(0, k)
  • 后缀:S中最靠的k个字符 S.suffix(k) = S.substr(n - k, k)
  • 文本串P:需要被查找的字符串
  • 模式串T:需要找的字符串(关键词)

接口

  • length() 返回串的长度
  • charAt(i) 返回给定下标位置的字符
  • substr(i, k) 截取 [i, i + k) 位置的字符串
  • prefix(k) S中最靠的k个字符
  • suffix(k) S中最靠的k个字符
  • concat(T) 在当前字符串后面连接一个字符串
  • equal(T) 比较两个字符串是否相等

问题

  • 模式串是否出现?
  • 首次在哪里出现?
  • 总共出现几次?
  • 各出现在哪里?

串匹配算法效率评测标准

我们可以随机生成文本串和模式串进行匹配来评测串匹配算法的效率吗? 我们应该将随机生成的数据的匹配结果分为匹配成功和匹配失败,分别测试。这是因为随机生成的数据对于串匹配来说失败的概率很大,失败时的效率会掩盖成功时的效率。随机生成的数据匹配成功与否一般还与字符的种类相关,比如二进制的字符串就比字母组合的字符串较容易匹配成功。


蛮力匹配算法

对于有一定编程基础的人遇到这个问题,都很容易想到这个算法。很简单,我们需要假定文本串的某个位置是模式串的头,向后匹配两者,如果遇到不匹配的字符就说明这个头不对。我们遍历文本串上所有可能成为模式串头的位置(下标在S.length()-P.length()之前的字符),最终就可以得出结果。

版本1

Ubuntu Pastebin : https://paste.ubuntu.com/p/y6QZ2sFY8Q/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int match(string P, string T)
{
int size_n = T.length(), i = 0;
int size_m = P.length(), j = 0;

while( j < size_m && i < size_n){
//从左向右逐个比对字符
if(T[i] == P[i]){ i++; j++;}
//若匹配,则转到下一个字符
else{ i -= j-1; j = 0;}
//否则,模式串T回退,文本串P复位
}

return i - j;
}

如果匹配成功返回 i - j ,即模式串头在文本串中的位置下标。如果没有匹配成功,说明循环因为i < size_n退出,此时i = size_n 而,返回值 i - j 将大于 size_n - size_m。调用者只需一步判断即可。

版本2

Ubuntu Pastebin : https://paste.ubuntu.com/p/n88Jkz2ypM/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int match(string P, string T)
{
int size_n = T.length(), i;
int size_m = P.length(), j;

for( i = 0; i < size_n - size_m + 1; i++){
//遍历所有可能成为模式串头的元素
for( j = 0; j < size_m; j++){
//假设T[i]为P[i]头逐个比对
if(T[i + j] != P[j]) break;
//如果有一个失配,说明此假设不对
}
if(j >= size_m) break; //找到匹配子串
}

return i;
}

版本2的实现更容易理解,它就如之前讲解的想法是一样的。


时间复杂度分析

这两种实现其实思想和效率都是一样的。接下来我们分析一下它们的时间复杂度

  • 最好情况(只经过一轮比对,即可确定匹配成功):O(size_m)
  • 最坏情况(每轮都对比至P的末字符,且反复如此):O(m (size_n - size_m + 1)) 一般 m << n 复杂度近似为 O(n m)

最坏情况是否会出现?

这里举个例子:

文本串:00000000…00000001

模式串:00001

最坏情况的特点

  • 最坏情况出现的概率与字母表的大小有关,字母表越小越容易出现局部匹配的情况导致浪费大量时间
  • size_m 越大,最坏情况出现的后果越严重

本文标题:串匹配算法1——蛮力匹配

文章作者:赵砚潇

发布时间:2018年02月21日 - 22:02

最后更新:2018年07月05日 - 01:07

原始链接:https://blog.zyx.sh/2018/02/21/strma-1/

许可协议: 署名-非商业性使用-相同方式分享 4.0 国际 转载请保留原文链接及作者。

Donate comment here