深入串的模式匹配算法(普通算法和KMP算法)的详解

串的定位操作通常称作串的模式匹配，是各种处理系统中的最重要操作之一。
模式匹配最朴素的算法是回溯法，即模式串跟主串一个字符一个字符的匹配，当模式串中跟主串不匹配时，主串回溯到与模式串匹配开始的下一个位置，模式串回溯到第一个位置，继续匹配。算法的时间复杂度为O（m*n），算法如下：


代码如下:

//朴素的串的模式匹配算法，S为主串，T为模式串，即找S中有没有与T相同的字串
int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替
{
 int i=pos, j=0;
 while(i <strlen(S) && j <strlen(T))//确保未超出字符串的长度
 {
  if (S[i] == T[j])
      { ++i; ++j;} //如果相同，则继续向后比较
  else
      {i = i-j+1; j =0;} //如果不同，就回溯，重新查找
 }
 if (j == strlen(T))
  return i-strlen(T); //若匹配成功，返回S中与T字符串相同开始位置的索引
 else return 0; //若匹配不成功，返回0
}

O（m*n）的时间复杂度有点大，于是人们发现了KMP算法，核心思想是：当不匹配发生时，主串不回溯，模式串回溯到“合适”的位置，哪个位置合适，只与模式串有关，所以可以先算出模式串中各个字符，当不匹配发生是，应该回溯到哪个位置。算法整体时间复杂度O(m+m)。
算法如下：


代码如下:

void GetNext(char* T, int *next)
{
 int i=1,j=0;
 next[1]=0;
 while( i < strlen(T) )
 {
  if (j == 0 || T[i] == T[j])
  {
    ++i; ++j;
    next[i] = j;
  }
  else j = next[j];
 }
}
int KMP(char* S, char* T, int pos)
{
 int i = pos, j = 1;
 while (i)
 {
  if (S[i] == T[j])
  {
   ++ i;  ++ j;
  }
  else
   j = next[j];
 }
 if (j > strlen(T))
  return i-T[0];
 else
  return 0;
}

求next的操作不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：


代码如下:

void GetNextEx(char *T, int *next)
{
 int i=1,j=0; next[1] = 0;
 while(i < strlen(T))
 {
  if (j == 0 || T[i] == T[j])
  {
   ++i; ++j;
   if (T[i] == T[j])
    next[i] = next[j];  //减少回退次数
   else   next[i] = j;  //和上面算法一样next[i]=j
  }
  else j = next[j];
 }
}

赞 (0)

相关推荐

  • 字符串的模式匹配详解--BF算法与KMP算法

    一.BF算法     BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果. 举例说明: S: ababcababa P: ababa BF算法匹配的步骤如下 i=0 i=1 i=2 i=3 i=4 第一趟:ababcababa 第二趟:ababcababa 第三趟:ababcababa 第四趟:ababcabab

  • 扩展KMP算法(Extend KMP)

    扩展kmp既是求模式串和主串的每一个后缀的最长公共前缀 即令s[i]表示主串中以第i个位置为起始的后缀,则B[i]表示s[i]和模式串的最长公共前缀 显然KMP是求s[i]=模式串长度的情况,所以,扩展KMP是对KMP的拓展 像求KMP的next数组一样,我们先求A[i],表示模式串的后缀和模式串的最长公共前缀 然后再利用A[i]求出B[i] 说明一下A的求法,B同理 现在我们要求A[i],且A[1]---A[i-1]已经求出,设k,且1<=k<=i-1,并满足k+A[k]最大 所以T[k]-

  • c语言中使用BF-KMP算法实例

    直接上代码 复制代码 代码如下: #define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h> #define MAX_SIZE 255    //定义字符串的最大长度 typedef unsigned char SString[MAX_SIZE];//数组第一个保存长度//BFint BFMatch(char *s,char *p){    int i,j;  

  • python实现的二叉树算法和kmp算法实例

    主要是:前序遍历.中序遍历.后序遍历.层级遍历.非递归前序遍历.非递归中序遍历.非递归后序遍历 复制代码 代码如下: #!/usr/bin/env python#-*- coding:utf8 -*- class TreeNode(object):    def __init__(self, data=None, left=None, right=None):        self.data = data        self.left = left        self.right =

  • C语言实现字符串匹配KMP算法

    C语言实现字符串匹配KMP算法

    字符串匹配是计算机的基本任务之一. 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KMP算法的解释步骤 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较.因为B与A不匹配,所以搜索词后移一位. 2. 因为B与A不匹配,搜索词再往后移. 3. 就这样,直到字符

  • JAVA实现KMP算法理论和示例代码

    一.理论准备KMP算法为什么比传统的字符串匹配算法快?KMP算法是通过分析模式串,预先计算每个位置发生不匹配的时候,可以省去重新匹配的的字符个数.整理出来发到一个next数组, 然后进行比较,这样可以避免字串的回溯,模式串中部分结果还可以复用,减少了循环次数,提高匹配效率.通俗的说就是KMP算法主要利用模式串某些字符与模式串开头位置的字符一样避免这些位置的重复比较的.例如 主串: abcabcabcabed ,模式串:abcabed.当比较到模式串'e'字符时不同的时候完全没有必要从模式串开始位

  • 基于KMP算法JavaScript的实现方法分析

    算法的核心是部分匹配表和回退算法,部分匹配表的实现如下: 复制代码 代码如下: function kmpGetStrPartMatchValue(str) {    var prefix = [];    var suffix = [];    var partMatch = [];    for(var i=0,j=str.length;i<j;i++){        var newStr = str.substring(0,i+1);        if(newStr.length ==

  • 深入串的模式匹配算法(普通算法和KMP算法)的详解

    串的定位操作通常称作串的模式匹配,是各种处理系统中的最重要操作之一.模式匹配最朴素的算法是回溯法,即模式串跟主串一个字符一个字符的匹配,当模式串中跟主串不匹配时,主串回溯到与模式串匹配开始的下一个位置,模式串回溯到第一个位置,继续匹配.算法的时间复杂度为O(m*n),算法如下: 复制代码 代码如下: //朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替{

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

  • C++实现查找中位数的O(N)算法和Kmin算法

    本文实例讲述了C++实现查找中位数的O(N)算法和Kmin算法,分享给大家供大家参考.具体方法如下: 利用快速排序的partition操作来完成O(N)时间内的中位数的查找算法如下: #include <iostream> #include <cassert> #include <algorithm> #include <iterator> using namespace std; int array[] = {1, 2, 10, 8, 9, 7, 5};

  • vue vue-Router默认hash模式修改为history需要做的修改详解

    主要是因为活动页会存在pc端的时候未登录的用户也需要访问的问题,因为未登录用户在活动页面进行操作的时候会触发到登录事件,然后我们实现的方式是通过接口来判断,该接口标记的是一个upn的值 然后登录的时候是单点登录,不知道是否回调地址不支持vue形式下hash模式的路由,因而自动忽视了后面的#路径 然后我查了一下一般回调以后#后都会默认为书签,我转义了然而还是只能职别#之前的路径 由于不是很清楚登录单点那一块而且他们暂时实现没有什么业务问题(当然开始~~就是不稳定,现在有时候还是会有不稳定的问题)所

  • 对Python的交互模式和直接运行.py文件的区别详解

    看到类似C:\>是在Windows提供的命令行模式,看到>>>是在Python交互式环境下. 在命令行模式下,可以执行python进入Python交互式环境,也可以执行python hello.py运行一个.py文件,但是在Python交互 式环境下,只能输入Python代码执行. Python的交互模式和直接运行.py文件有什么区别呢? 直接输入python进入交互模式,相当于启动了Python解释器,但是等待你一行一行地输入源代码,每输入一行就执行一行. 直接运行.py文件相当

  • 发布订阅模式在vue中的实际运用实例详解

    订阅发布模式定义了一种一对多的依赖关系,让多个订阅者对象同时监听某一个主题对象.这个主题对象在自身状态变化时,会通知所有订阅者对象,使它们能够自动更新自己的状态. 比如addEventListener 这个api就是个发布订阅模式 如果用过vue的同学,可以把他类比于 watch 下面我们看一个例子 var observe={ fnsObj:{}, // 订阅方法 on:function(key,fn){ if(!observe.fnsObj[key]){ observe.fnsObj[key]

  • JavaScript策略模式利用对象键值的映射关系详解

    目录 引言 1.策略模式的极简实现 2.策略模式的简单案例 (1)工具函数 (2)提示样式 总结 引言 策略模式指的是,定义一系列的算法,把它们一个个的封装起来,通过传递一些参数,使他们可以相互替换. 举个周末从家去咖啡馆的例子: 从家去咖啡馆,有跑步.骑行和漫步的方式.也就是说,从家到咖啡馆,有三种策略可选择. 1.策略模式的极简实现 通过对象的键值映射关系,定义策略和具体实现之间的关系: var strategies = { A: xxx, B: yyy, C: zzz } 其中,A.B和C

  • JavaScript严格模式下关于this的几种指向详解

    JavaScript严格模式下关于this的几种指向详解

    前言 相信不少人在学习或者使用Javascript的时候,都曾经被 JavaScript 中的 this 弄晕了,那么本文就来整理总结一下在严格模式下 this 的几种指向. 一.全局作用域中的this 在严格模式下,在全局作用域中,this指向window对象 "use strict"; console.log("严格模式"); console.log("在全局作用域中的this"); console.log("this.docume

  • PHP设计模式之策略模式（Strategy）入门与应用案例详解

    PHP设计模式之策略模式（Strategy）入门与应用案例详解

    本文实例讲述了PHP设计模式之策略模式(Strategy)入门与应用.分享给大家供大家参考,具体如下: 这个策略模式,意思就是定义一系列算法,把它们一个个封装起来,并且使它们可相互替换,使用得算法的变化可独立于使用它的客户,简单来讲就是,策略模式设计帮助构建的对象不必自身包含逻辑,而是能够根据需要利用其他对象中的算法. 来看下应用场景: 1. 多个类只区别在表现行为不同,可以使用Strategy模式,在运行时动态选择具体要执行的行为. 2. 需要在不同情况下使用不同的策略(算法),或者策略还可能

随机推荐