正文

常用算法3 - 字符串查找/模式匹配算法（BF & KMP算法）

IP云
IP云V管理员/5 阅读
10/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

相信我们都有在linux下查找文本内容的经历，比如当我们使用vim查找文本文件中的某个字或者某段话时，Linux很快做出反应并给出相应结果，特别方便快捷！

那么，我们有木有想过linux是如何在浩如烟海的文本中正确匹配到我们所需要的字符串呢？这就牵扯到了模式匹配算法！

1. 模式匹配

什么是模式匹配呢？

  • 模式匹配，即子串P(模式串)在主串T(目标串)中的定位运算，也称串匹配

假设我们有两个字符串：T(Target, 目标串)和P(Pattern, 模式串)；在目标串T中查找模式串T的定位过程，称为模式匹配.

模式匹配有两种结果：

  • 目标串中找到模式为T的子串，返回P在T中的起始位置下标值；
  • 未成功匹配，返回-1

通常模式匹配的算法有很多，比如BF、KMP、BM、RK、SUNDAY等等，它们各有千秋，我们此处重点讲解BF和KMP算法(因为比较常用)

2. BF算法

BF，即Brute-Force算法，也称为朴素匹配算法或蛮力算法，效率较低！

1). 算法思想

基本思想：

    1. 将目标串T第一个字符与模式串P的第一个字符比较；
    1. 若相等，则比较T和P的第二个字符
    1. 若不等，则比较T的下一个字符与P的第一个字符
    1. 重复步骤以上步骤，直到匹配成功或者目标串T结束

流程图如下：

例如：

设 T=‘ababcabcacbab', P='abcac', 匹配流程

  • Step 1: 主串T与子串P做顺序比较，当比较到位置2时，主串T[2]='a'与子串P[2]='c'不等(蓝色阴影表示)，记录各自的结束位置，并进入Step 2
  • Step 2: 主串T后移一位，主串T与子串P再从头开始比较，比较如Step 1
  • Step 3: 每次比较，子串都从0开始，主串的开始位置与上次的结束位置存在一定的关系；在某些时候需要“回溯”(上次比较结束的位置要向前移动)；如Step 1的结束位置为2，Step 2的开始位置为1；Stp3的结束位置为6，Step 4的开始位置为3等；
  • Step 4: 主串T的索引值i 与 子串P的索引值j的关系为：i=i-j+1

2). 代码实现

/*-----------------------------------------------------------------------------
* Function: BF - Does the P can be match in T
* Input: Pattern string P, Target string T
* Output: If matched: the index of first matched character
* else: -1
-----------------------------------------------------------------------------*/
int BF(const string &T, const string &P)
{
int j=0, i=0, ret=0; while((j < P.length()) && (i<T.length()))
{
if(P[j] == T[i]) //字符串相等则继续
{
i++;
j++; //目标串和子串进行下一个字符的匹配
}
else
{
i = i - j + 1;
j = 0; //如果匹配不成功，则从目标字符串的下一个位置开始从新匹配
}
} if(i < T.length()) //若匹配成功，返回匹配的第一个字符的下标值
ret = i - P.length() ;
else
ret = -1; return ret;
}

3). 效率分析

效率分析主要是分析时间复杂度和空间复杂度. 而本例的空间复杂度较低，暂时不做考虑，我们来看看时间复杂度。

分析时间复杂度通常是分析最坏情况，对于BF算法来说，最坏情况举例如下：

T="ggggggggk", P="ggk"



由上图可知，第i次匹配，前面第i-1次匹配，每次都需要比较m次(m为模式串P的长度)，因此为(i-1)m次；第i次匹配成功也需要m次比较，因此总共需要比较mi次。

对于长度为n的主串T，i=n-m+1,每次匹配成功的概率为Pi，且概率相等；则在最坏情况下，匹配成功的概率Cmax可表示为：




一般情况下 n>>m,因此，BF的时间复杂度为 O(m*n)

3. KMP算法

BF算法每次都需要回溯，导致时间复杂度较大，那么有没有一种效率更高的模式匹配算法呢？

答案是肯定的，那就是KMP算法。

1). 名词解释

在进行算法讲解之前，必须要明确以下几个名词，否则无法理解此算法

  • 目标串 T: 即大量的等待被匹配的字符串
  • 模式串 P：即我们需要查找的字符串
  • 字符串前缀：字符串的任意首部(不包括最后一个字符)；如"abcd"的前缀为"a","ab","abc",但不包括"abcd"
  • 字符串后缀：字符串的任意尾部(不包括第一个字符)；如"abcd"的后缀为"d","cd","bcd",但不包括"abcd"
  • 字符串前后缀相等位数k：即前缀与后缀的最长匹配位数，

2). 算法思想

KMP算法的核心思想是：部分匹配，即不再把主串的位置移动到已经比较过的位置(不再回溯)，而是根据上一次比较结果继续后移。

概念相当抽象，那么我们以例子来解释：

  • Step 1: 匹配到索引值index=2时，匹配失败
  • Step 2: 匹配的开始位置为index=2(没有回溯到1), 原因如下：

Step 1 比较后，已知T[1]='b', S[0]='a'，理论上已经比较过了，所以无需回溯再次比较

Step 2 一直进行匹配，直到T[6]时刻失配.

  • Step 3: T的位置不进行回溯，还是保持在T[6]开始(KMP算法规定：目标串T不回溯，上一次的结束位置即为下一次的开始位置)；

    P的索引值从1开始而非0，原因如下：

在Step 2 中，T[5]='a'已经比较过，我们已知，且与P[3]相等；因为P[0]==P[3]，所以无需比较P[0]与T[5]，因为Step 2 理论上已经进行了比较(其实就是看子串P Step2结束位置P[4]之前的P[0-3]的字符串前后缀相等位数k，使得P[k]与上次主串的结束位置T[6]对齐)

由以上分析可知，KMP算法过程中关键点就是求： 子串P结束位置前的前后缀相等位数k。

下图是模式串P="abcabca"的前后缀关系分析(包括前后缀字符串相等位数k)

由上图我们可以给出，T串每一个字符做结束位置时，下一次的开始位置的值；

  • j 为T的本次匹配结束位置(失配位置);
  • next[j] 为下次匹配模式串P的开始位置



PS: next[j]就是前后缀字符串相等位数k

根据上面的讨论，我们可以得出next[j]的运算公式：



其中，-1 是一个标记，标识下一次的开始位置目标串为,模式串P为

如果以上你没有明白，不要紧的，只需要记住next[j]的函数就可以，其它一切都是根据它来的！

3). 代码实现

/*-----------------------------------------------------------------------------
* Function: KMP- Does the P can be match in T
* Input: Pattern string P, array next
* Output: If matched: the index of first matched character
* else: -1
-----------------------------------------------------------------------------*/
void getNext(const string &P, int next[])
{
int j=0; //模式串P的下标值/索引值
int k=-1; //模式串P的前缀和后缀串相等的位数
next[0]=-1; //置初值 while(j < P.length())
{
if((k == -1) || (P[j] == P[k])) //从模式串P的开始位置处理 或 顺序比较主串和子串
{
j++;
k++;
next[j] = k;
} else //设置重新比较位置：j串不变，k串从next[k]位置开始
k = next[k];
}
}/*-----------------------------------------------------------------------------
* Function: KMP- Does the P can be match in T
* Input: Pattern string P, Target string T
* Output: If matched: the index of first matched character
* else: -1
-----------------------------------------------------------------------------*/
int KMP(const string &T, const string &P)
{
int next[MaxSize]={0};
int i=0; //目标串T的下标值/索引值
int j=0; //模式串P的下标值/索引值
int ret=0; getNext(P, next); //获取模式串P的next数组 int PLen = P.length();
int TLen = T.length(); while((i < T.length()) && (j < PLen)) //奇怪，此处我用 j<P.length()就不行，待解决
{
if((j==-1) || (P[j] == T[i])) //j=-1表示首次比较
{
i++;
j++;
} else
{
j = next[j];
}
} if(j >= P.length())
ret = i-P.length();
else
ret = -1; return ret;
}

4). 效率分析

由于KMP算法不回溯，比较是顺序进行的，因此最坏情况下的KMP时间复杂度为 O(m+n).

其中，m为模式串P的字符串长度，n为目标串T的字符串长度.

常用算法3 - 字符串查找/模式匹配算法（BF & KMP算法）的更多相关文章

  1. 【算法】串的模式匹配算法（KMP）

    串的模式匹配算法     问题:         求子串位置的定位函数如何写? int index(SString S,SString T,int pos);         给定串S,子串T,问T在 ...

  2. 字符串与模式匹配算法（一）：BF算法

    一.BF算法的基本思想 BF(Brute Force)算法是模式匹配中最简单.最直观的算法.该算法最基本的思想是从主串的第 start 个字符起和模式P(要检索的子串)的第1个字符比较,如果相等,则逐 ...

  3. Python 细聊从暴力（BF）字符串匹配算法到 KMP 算法之间的精妙变化

    1. 字符串匹配算法 所谓字符串匹配算法,简单地说就是在一个目标字符串中查找是否存在另一个模式字符串.如在字符串 "ABCDEFG" 中查找是否存在 "EF" ...

  4. 数据结构学习之字符串匹配算法&lpar;BF&vert;&vert;KMP&rpar;

    数据结构学习之字符串匹配算法(BF||KMP) 0x1 实验目的 ​ 通过实验深入了解字符串常用的匹配算法(BF暴力匹配.KMP.优化KMP算法)思想. 0x2 实验要求 ​ 编写出BF暴力匹配.KM ...

  5. 字符串匹配算法之 kmp算法 （python版）

    字符串匹配算法之 kmp算法 (python版) 1.什么是KMP算法 KMP是三位大牛:D.E.Knuth.J.H.MorriT和V.R.Pratt同时发现的.其中第一位就是<计算机程序设计艺 ...

  6. 动画演示Sunday字符串匹配算法——比KMP算法快七倍！极易理解！

    前言 上一篇我用动画的方式向大家详细说明了KMP算法(没看过的同学可以回去看看). 这次我依旧采用动画的方式向大家介绍另一个你用一次就会爱上的字符串匹配算法:Sunday算法,希望能收获你的点赞关注收 ...

  7. 字符串的模式匹配算法——KMP模式匹配算法

    朴素的模式匹配算法(C++) 朴素的模式匹配算法,暴力,容易理解 #include<iostream> using namespace std; int main() { string m ...

  8. 字符串匹配算法之————KMP算法

    上一篇中讲到暴力法字符串匹配算法,但是暴力法明显存在这样一个问题:一次只移动一个字符.但实际上,针对不同的匹配情况,每次移动的间隔可以更大,没有必要每次只是移动一位: 关于KMP算法的描述,推荐一篇博 ...

  9. 串的两种模式匹配方式（BF&sol;KMP算法）

    前言 串,又称作字符串,它是由0个或者多个字符所组成的有限序列,串同样可以采用顺序存储和链式存储两种方式进行存储,在主串中查找定位子串问题(模式匹配)是串中最重要的操作之一,而不同的算法实现有着不同的 ...

随机推荐

  1. rsync命令详解

    介绍 rsync命令是一个远程数据同步工具,可通过LAN/WAN快速同步多台主机间的文件.rsync使用所谓的“rsync算法”来使本地和远程两个主机之间的文件达到同步,这个算法只传送两个文件的不同部 ...

  2. 《JAVA NIO》读书笔记

    第一章 简介 第二章 缓冲区 第三章  channel

  3. asp&period;net 时间比较，常用于在某段时间进行操作

    DateTime.Compare(t1,t2)比较两个日期大小,排前面的小,排在后面的大,比如:2011-2-1就小于2012-3-2返回值小于零:  t1 小于 t2. 返回值等于零 : t1 等于 ...

  4. uva 10986

    ford 超时  使用优先队列的Dijkstra 算法 //#include <cstdio> //#include <cstring> //#include <algo ...

  5. （三）JAVA使用POI操作excel

    1,单元格对齐方式 Demo8.java package com.wishwzp.poi; import java.io.FileOutputStream; import java.util.Date ...

  6. &lbrack;DEncrypt&rsqb; DESEncrypt--加密&sol;解密帮助类 （转载）

    点击下载 DESEncrypt.zip 这个类是关于加密,解密的操作,文件的一些高级操作1.DESEncrypt加密2.DESEncrypt解密看下面代码吧 /// <summary> / ...

  7. Bootstrap 模态对话框只加载一次 remote 数据的解决办法

    原文: https://my.oschina.net/qczhang/blog/190215?p=1

  8. PHP 中使用 Composer

    在线安装版本: http://www.phpcomposer.com/ 这个是国内的composer网站 thinkphp5自带了composer.phar组件,如果没有安装,则需要进行安装 以下命令 ...

  9. Expo大作战&lpar;二十一&rpar;--expo如何分离（detach），分离后可以比react native更有优势，但也失去了expo的部分优势，

    简要:本系列文章讲会对expo进行全面的介绍,本人从2017年6月份接触expo以来,对expo的研究断断续续,一路走来将近10个月,废话不多说,接下来你看到内容,讲全部来与官网 我猜去全部机翻+个人 ...

  10. 【BZOJ2830&sol;洛谷3830】随机树（动态规划）

    [BZOJ2830/洛谷3830]随机树(动态规划) 题面 洛谷 题解 先考虑第一问. 第一问的答案显然就是所有情况下所有点的深度的平均数. 考虑新加入的两个点,一定会删去某个叶子,然后新加入两个深度 ...