扩展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]--T[k+A[k]-1]=T[0]--T[A[k]-1]，推出T[i]--T[k+A[k]-1]=T[i-k]--T[A[k]-1]
令L=A[i-k]，若L+i-1<k+A[k]-1，由A是最长公共前缀知A[i]=L，否则，向后匹配，知道字符串失配
并相应更新k
时间复杂度为线性O(m+n)

while(1+j<strlen(T)&&T[0+j]==T[1+j])
        j = j + 1;
 A[1]=j;
    int k=1;
    for(int i=2; i<strlen(T); i++)
    {
        int Len = k + A[k] - 1,L = A[i-k];
        if( L < Len - i + 1 )
            A[i] = L;
        else
        {
            j = max(0,Len -i +1);
            while(i+j<strlen(T)&&T[i+j] == T[0+j])
                j = j + 1;
            A[i] = j,k = i;
        }
    }
    j = 0;
    while(j<strlen(S)&&j<strlen(T)&&T[0+j]==S[0+j])
        j = j + 1;
    B[0] = j,k = 0;
    for(int i=1; i<strlen(S); i++)
    {
        int Len = k + B[k] - 1,L = A[i-k];
        if( L < Len - i + 1 )
            B[i] = L;
        else
        {
            j = max(0,Len -i +1);
            while(i+j<strlen(S)&&j<strlen(T)&&S[i+j] == T[0+j])
                j = j + 1;
            B[i] = j,k = i;
        }
    }
 ps:普通的next是到这个结尾的，能和模式串匹配的长度，扩展kmp是以这个开头的能匹配的最大长度
pss:然后我简单比较了下kmp和扩展kmp http://www.isnowfy.com/kmp-and-extend-kmp/

赞 (0)

相关推荐

  • 基于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 ==

  • 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 =

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

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

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

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

  • 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;  

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

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

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

  • 扩展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]-

  • java暴力匹配及KMP算法解决字符串匹配问题示例详解

    java暴力匹配及KMP算法解决字符串匹配问题示例详解

    目录 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 二.KMP算法 算法介绍 一个图例介绍KMP算法   代码实现 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD";     1. S[0]为B,P[0]为A,不匹配,执行第②条指令:"如果失配(即S[i]! = P[j]),令i = i - (j - 1),

  • Java数据结构之KMP算法详解以及代码实现

    目录 暴力匹配算法(Brute-Force,BF) 概念和原理 next数组 KMP匹配 KMP全匹配 总结 我们此前学了前缀树Trie的实现原理以及Java代码的实现.Trie树很好,但是它只能基于前缀匹配实现功能.但是如果我们的需求是:一个已知字符串中查找子串,并且子串并不一定符合前缀匹配,那么此时Trie树就无能为力了. 实际上这种字符串匹配的需求,在开发中非常常见,例如判断一个字符串是否包括某些子串,然后进行分别的处理. 暴力匹配算法(Brute-Force,BF) 这是最常见的算法字符

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

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

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

  • KMP算法精解及其Python版的代码示例

    KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题.算法名称来源于发明者Knuth,Morris,Pratt. 假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm). 朴素的字符串查找方法 从字符串S的第一个字符开始与M进行比较,如果匹配失败.从下一字符开始,重新比较.指导第 (ls - lm) 个字符. 这种方法容易想到并且容易理解,效率不高. 问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些. KMP的字符串查找方法 假定在模式

  • C语言中实现KMP算法的实例讲解

    一般的算法为什么这么低效呢?那是因为主串指针回溯情况过多: 主串指针如果不回溯的话,速度就会加快,那我们就会想: 如何让主串指针不回溯? KMP算法就是解决了这个问题,所以速度变得更快速了. 它是这样子的: 用一个数组:next[] 求得失配时的位置,然后保存下来. 要说清楚KMP算法,可以从朴素的模式匹配算法说起.  朴素的模式匹配算法比较容易理解,其实现如下 int Index(char s[], char p[], int pos) { int i, j, slen, plen; i =

  • JavaScript中数据结构与算法(五)：经典KMP算法

    JavaScript中数据结构与算法(五)：经典KMP算法

    KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右 后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右. 通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上蛋疼的KMP是讲解很多,基本都是走的高大上路线看的你也是一头雾水,我试图用自己的理解用最接地气的方式描述 KMP KMP也是一种优化版的

随机推荐