精华内容
下载资源
问答
  • 大多数据结构课本中,涉及的内容即的模式匹配,需要掌握的是朴素算法KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。

    本文的逻辑顺序为
    1、最基本的朴素算法
    2、优化的KMP算法
    3、应算法需要定义的next值
    4、手动写出较短串的next值的方法
    5、最难理解的、足足有5行的代码的求next值的算法
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…

    一、问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    二、朴素算法

    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:

    在这里插入图片描述
    这个算法简单,不多说,附上代码

    #include<stdio.h>
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
        if(sLen<pLen)return 0;
        int i = 1,j = 1;
        while(i<=sLen && j<=pLen){
            if(s[i]==p[j]){i++;j++;}
            else{
                i = i-j+2;
                j = 1;
            }
        }
        if(j>pLen) return i-pLen;
        return 0;
    }
    void main(){
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
        char p[]={' ','a','b','a','a','b','c','a','c'};
        int sLen = sizeof(s)/sizeof(char)-1;
        int pLen = sizeof(p)/sizeof(char)-1;
        printf("%d",Index_1(s,sLen,p,pLen));
    }
    

    三、改进的算法——KMP算法

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    在这里插入图片描述

    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。

    相比朴素算法:
    朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高

    而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)

    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)

    • 比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      在这里插入图片描述

    • 假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
      在这里插入图片描述

    • 那么可以推出,P1…Pk-1与Si…Si+j-2
      在这里插入图片描述

    • 显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
      在这里插入图片描述

    • 为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。

    • 最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。

    四、手动写出一个串的next值

    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    在这里插入图片描述
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。

    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    在这里插入图片描述

    五、求next的算法

    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。

    int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
        next[1] = 0;
        int i = 1,j = 0;
        while(i<=cLen){
            if(j==0||ch[i]==ch[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    • 还是先由一般再推优化:
      直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
      根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
      不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
      if(P1…Pj-1 == P2…Pj) => next[j+1]=j
      else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
      else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2



      else if(P1P2 == Pj-1Pj) => next[j+1]=3
      else if(P1 == Pj-1) => next[j+1]=2
      else if(P1 != Pj-1) => next[j+1]=1

      每次前去尾1个,后掐头1个,直至得到next[j+1]

    • 再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组
      但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
      ①next[j+1]的可能的最大值是多少(即从哪开始验证)
      ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
      看一下的分析:

    1、next[j+1]的最大值为next[j]+1。
    因为:
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    这里不好解释,直接看下面的流程分析及图解

    开——始——划——重——点!
    从头走一遍流程
    ①求next[j+1],设值为m
    已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
    如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    ⑤第二第三步联合得到:
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推

    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1、要求next[k+1] 其中k+1=17
    在这里插入图片描述
    2、已知next[16]=8,则元素有以下关系:
    在这里插入图片描述
    3、如果P8=P16,则明显next[17]=8+1=9
    4、如果不相等,又若next[8]=4,则有以下关系

    在这里插入图片描述
    又加上2的条件知
    在这里插入图片描述
    主要是为了证明:
    在这里插入图片描述
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    6、若next[4]=2,则有以下关系
    在这里插入图片描述
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!

    展开全文
  • 一、KMP字符串匹配算法 1. KMP算法简介 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。 KMP算法的核心是利用匹配失败...

    一、KMP字符串匹配算法

    1. KMP算法简介

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.MorrisV.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
    KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
    具体实现就是通过一个 next() 函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

    2. KMP算法过程图解

    1. 首先给定主字符串S和匹配字符串T,开始进行匹配
    在这里插入图片描述
    2. 我们发现第五个字符不匹配,假如按照BF算法匹配的话,那么接下来几步如图:
    在这里插入图片描述
    在这里插入图片描述

    3. 然而事实上我们从最开始就可以发现,字符串T中存在相同子串ab,如图
    在这里插入图片描述
    4. 所以我们应该这样移动匹配位置,与BF算法相比一下,显然这种办法比BF快了很多很多步。
    在这里插入图片描述
    5. 简单思考一下
    (1)当S串的字符d 和 T串的字符c 发生不匹配的时候,也就意味着之前abab都匹配相同,
    (2)即T串的前四个字符和S串i位置之前的四个字符是相同的
    (3)所以换言之我们只需要考虑T串任意位置前的子串中是否存在相同的前缀和后缀及其最大长度,即可快速定位下一次移动位置
    在这里插入图片描述

    6. 这时候我们就可以单独将T串拿出来考虑,如图假设第五个字符发生不匹配的时候,我们就可以定位到最长的相同前缀后缀长度=2(ab)的后面一个位置,即j=2+1(如果下标从0开始,则j = 2)。
    在这里插入图片描述
    7. 所以我们最后需要考虑的就是如何求出T串中,每一个位置发生不匹配时,在此位置之前的子串中,最长的相同前后缀长度,并用数组 next[ ]存储该位置,这样我们就可以快速定位下次的匹配位置
    在这里插入图片描述

    3. next[ ]数组求解过程

    1. 开始我们设置 next[1] = 0(第一个字符就不匹配),用i=1,j=0两个指针对匹配串进行遍历,如图:
    在这里插入图片描述

    2. next[ ](数组下标从0开始)的计算分为两种情况
    (1)当T[i] == T[j] || j == -1时, 且next[++i] =++j,如图所示,意思是如果T[3] == T[8]时,那么当i = 8+1位置不匹配时,我们需要跳转到j = 3+1的位置,即next[9] = 4,也就是求出了[1,i]之间的最大相同前后缀长度。
    在这里插入图片描述
    (2)当T[i] != T[j] && j != 0,则j = next[j]
    在这里插入图片描述

    4. 源代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    void Next(int *next, char *T)
    {
    	next[0] = -1;	//首个字符不存在最大相同前后缀长度
    	int i = 0, j = -1, len = strlen(T);
    	//寻找最大前后缀长度
    	while(i < len)
    	{
    		if(j == -1 || T[i] == T[j])	
    		{
    			if(T[++i] != T[++j])
    				next[i] = j;
    			else
    				next[i] = next[j];			
    		}
    		else	//重新定位T[i] == T[j] 的匹配位置
    			j = next[j];
    	}
    }
    int KMP(char *S, char *T)
    {
    	int i = 0, j = 0;
    	int S_len = strlen(S);
    	int T_len = strlen(T);
    
    	//动态分配和T串同长的整形数组
    	int *next;
    	next = (int*)malloc(S_len*sizeof(int));
    
    	//求T串中每个位置之前子串的最大相同前后缀长度
    	Next(next, T);
    	
    	//利用next数组进行快速匹配
    	while(i < S_len && j < T_len)
    	{
    		if(j == -1 || S[i] == T[j])//重新开始匹配/匹配成功
    		{
    			i++;
    			j++;
    		}
    		else				//匹配失败,重新定位T串的指针位置
    			j = next[j];
    	}
    	if(j >= T_len)			//当匹配指针等于T串长度时,证明S主串中存在T子串
    	{
    		return i - T_len;
    	}
    	else					//S主串不存在T子串
    		return 0;
    }
    
    int main()
    {
    	char S[100] = "adadafadfabaabcac", T[20]="abaabcac";
    	printf("%d\n", KMP(S, T));
    	return 0;
    }
    
    展开全文
  • KMP匹配算法

    2012-11-13 23:48:21
    KMP匹配算法就是匹配字符的时候指针主指针不回溯。此算法主要是算出模式每个字符应该移动的长度。在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]...

    串的KMP匹配算法就是匹配字符串的时候指针主串指针不回溯。此算法主要是算出模式串每个字符应该移动的长度。在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

    // KMP算法.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    
    int *KMP(char *str)
    {
    	int len=strlen(str);
    	int *next=(int*)malloc(sizeof(int)*len);
    	next[0]=-1;
    	int i=0,k=-1;
    	while(i<len)
    	{
    		if(k==-1||str[i]==str[k])
    		{
    			i++;
    			k++;
    			next[i]=k;
    		}
    		else
    		{
    		   k=next[k];
    		}
    	}
    	return next;
    }
    
    int macth(char* str,char *model)
    {
    	 int* next=KMP(model);
    	int i=0,j=0;
    	while (i<strlen(str))
    	{
    		if(j==-1||str[i]==model[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j=next[j];		
    		}
    		if(j>0&&j>=strlen(model))
    		{
    			return i-strlen(model);
    		}
    	}
    	
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	char *str="abcabcacaba";
    	char *model="aca";
    	int *a=KMP(str);
    	for(int i=0;i<strlen(str);i++)
    	{
    		printf("%d\n",a[i]);
    	}
    	cout<<"--------"<<endl;
    	cout<<macth(str,model);
    	return 0;
    }
    
    


     

     

     

     

    展开全文
  • KMP匹配算法

    2018-04-14 19:11:57
    在说KMP匹配算法之前,我们先来看看与它相近的另一种匹配算法,名曰“暴力匹配算法”1.暴力匹配算法(设有如下的两组字符)第一位不匹配,则向右移动一位,得到如下的形式B与A依旧不匹配,则继续往后移,当移到...

    在说KMP匹配算法之前,我们先来看看与它相近的另一种匹配算法,名曰“暴力匹配算法”

    1.暴力匹配算法(设有如下的两组字符串)

    第一位不匹配,则向右移动一位,得到如下的形式


    B与A依旧不匹配,则继续往后移,当移到如下的形式时:


    尽管之前的文本串和模式串已经分别匹配到了S[9]、p[5].但因为S[10]和p[6]不匹配,所以文本串会回溯到p[0].从而让是s[5]跟p[0]匹配(S[5]与p[0]肯定匹配失败,因为S[5] = p[1] = B     P[0] = A.所以S[5] != P[0])得到如下结果:


    然后又开始进行后移匹配。

    这块的算法代码为:

    if(S[i] == P[j])
    {
        i++;
        j++;
    }
    else
    {
        i = i-j+1;
        j = 0;
    }

    2.KMP匹配算法

    相对于暴力匹配算法的改进是引入了一个跳转表nex[];

    算法思路:

    (1)假设现在文本串S匹配到i位置,模式串P匹配到j位置

    (2)若j = -1,或者当前字符匹配成功(即S[i] == P[j])都令i++,j++继续匹配下一字符;

    (3)若j != -1,且当前字符匹配失败(即S[i] != P[j]),则令i不变 j = next[j](当匹配失败时,模式串向右移动的位数为:失配字符所在的位置 - 失配字符所对应的nex值,即移动的实际位数为j - next[j](当前字符串中有多大长度的相同前缀后缀)),如下表:

    模式串的单个子串前缀后缀最大公共元素长度
    A0
    ABAB0
    ABCDA,AB,ABCD,CD,BCD0
    ABCDAA,AB,ABC,ABCDA,DA,CDA,BCDA1
    ABCDABA,AB,ABC,ABCD,ABCDAB,AB,DAB,CDAB,BCDAB(长度为2)2
    ABCDABDA,AB,ABC,ABCD,ABCDA,ABCDABD,BD,ABD,DABD,CDABD,BCDABD0

    因此:


    第一位都不匹配,直接将模式串不断向右移一位,直到模式串中的字符A和文本中的第5个字符A匹配成功


    此时,匹配的字符数为6个,Next[j] = 2 ,j=6.所以:右移 j-Next[j] = 6-2 = 4个


    Next[j] = 0       j = 2       所以:右移 2-0 = 2位


    右移一位


    然后继续右移4位


    至此,文本串和字符串已经匹配成功

    具体算法:

    if(j == -1 || S[i] == P[j])
    {
        i++;
        j++;
    }
    else
    {
        j = Next[j];
    }





       

    展开全文
  • 第五章 KMP匹配算法

    千次阅读 2015-05-29 10:54:21
    一、的定义 (string)是由零个或多个字符组成的有限序列,又名叫字符。 一般记作: s="a1a2a3...an"; 字符的基本操作方法: 二、的存储结构 ...三、朴素的模式匹配算法 子串的定位操作通常称
  • 朴素模式匹配算法和KMP匹配算法 一、朴素模式 假设我们要从主S=”goodgoogle"中找到子串T=“google"的位置,步骤如下: i表示主的当前位置下标,j表示子串的当前位置下标,如上图在第一轮比较(i=1开始)中j=4...
  • 字符串匹配KMP算法

    千次阅读 2019-02-25 22:28:50
    我们都说KMP算法是一种高效的字符串匹配算法,所以首先先定义下字符匹配问题:给定一个文本T(也叫主S),和一个模式P,现在要找出S中与P匹配的子串,如果存在就返回匹配位置,否则返回-1。 暴力...
  • KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式与主的匹配...
  • KMP字符串匹配算法

    2018-11-24 23:56:31
    KMP字符串匹配算法
  • 多模式串匹配算法 Trie 树和 AC 自动机 KMP 算法 KMP 算法是根据三位作者(D.E.Knuth,J.H.Morris 和 V.R.Pratt)的名字来命名的,算法的全称是 Knuth Morris Pratt 算法,简称为 KMP 算法。 思想 1,KMP算法的核心...
  • KMP字符模式匹配算法

    千次阅读 2016-09-23 11:39:07
    KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: //在字符中查找指定字符的第一次出现,不能找到则返回-1 int strstr(char *S, char *T) {
  • 暴力算法 字符匹配最简单的方法是使用暴力算法,假设主的长度为m,子串的长度为n,那么暴力算法的时间复杂度是O((m-n+1)n),也即是O(mn),效率比较低下。 ...参考博客:KMP字符串匹配算法 ...
  • Java KMP匹配算法实现
  • KMP 算法 —— 字符串匹配算法

    千次阅读 多人点赞 2017-05-03 03:36:04
    字符串匹配常用算法KMP算法。那么,KMP算法是啥?如何(直观)理解大名鼎鼎的KMP算法
  • KMP串匹配算法

    2010-10-13 19:09:00
    KMP串匹配算法
  • 飘逸的python - 字符KMP匹配算法

    万次阅读 2014-11-10 11:20:27
    首先我们来看一下字符的朴素匹配. 可以想象成把文本s固定住,模式p从s最左边开始对齐,如果对齐的部分完全一样,则匹配成功,失败则将模式p整体往右移1位,继续检查对齐部分,如此反复. #朴素匹配 def naive_...
  • 本文用最简洁易懂的方式介绍了字符串匹配算法中的BF算法和KMP算法。本下一篇将继续介绍Horspool算法和BM算法。 现在我们用的大部分软件都含有查找/替换的功能,要完成查找替换功能就需要用到字符串匹配算法。字符...
  • 一、字符串匹配算法KMPKMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,...
  • 字符模式匹配算法--详解KMP算法

    千次阅读 热门讨论 2014-10-26 10:14:54
    在软考的复习中,看到过几次 字符的模式匹配算法。看起来挺难的。所以花了点时间查了查关于字符匹配的算法。下面详细介绍一下KMP模式匹配算法 以及next[j]函数如何计算。
  • KMP字符串匹配算法思悟

    千次阅读 2018-04-06 11:08:12
    KMP字符串匹配算法思悟 本文细致分析了KMP算法高效的原因以及KMP算法的实现原理; 源码github地址(这是我自己实现的相关算法(目前有排序算法和KMP算法),其中用到的数据结构也是自己实现的一套API,包括链表、...
  • 我们知道朴素模式匹配算法:http://blog.csdn.net/chfe007/article/details/43448655是很低效的,KMP算法从模式出发,发现模式中隐藏的信息来减少比较的次数,具体如何做到的可以移步这个链接:http
  • 字符匹配算法——BF算法和KMP算法,看了网上很多其他的相关资料,很多写的过于繁杂,因此重新写了篇。后续会进行文章维护
  • KMP-字符快速匹配算法

    千次阅读 2016-08-20 19:02:48
    之前一直保持在word文档中记录总结,最近发现C博客是个分享的好地方,记录自己学习总结的同时,也可以把总结拿出来分享,万一能帮到... 朴素字符串匹配算法时间复杂度为O(n*m),n/m分别为主/子串长度,而KMP算法的时间
  • -KMP模式匹配算法

    千次阅读 2017-03-17 22:47:43
    5.7 KMP 模式匹配算法 你们可以忍受朴素模式匹配算法的低效吗?也许不可以、也许无所谓。但在很多年前我们的科学家们,觉得像这种有多个0和1重复字符的字符,却需要挨个遍历的算法是非常糟糕的事情。于是有三位...
  •  这个算法理解起来有点难受,建议看下简单的模式匹配算法 BF算法 刷下经验,如上链接。 2.优化匹配算法:  相比于Brute-Force(BF算法),每当一趟匹配出现字符不等时,不需要回溯i指针(目标指针),并且...
  • KMP算法是一种改进的字符串匹配算法KMP算法的核心是利用匹配失败后的信息,尽量减少模式与主的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式的局部匹配信息。KMP...
  • 字符串匹配 KMP算法

    2020-02-06 13:30:14
    问题描述:字符串匹配即查找待匹配字符(模式...但暴力匹配效率比较低,经典算法KMP效率更高。 例:主s=“abcdeabcdxabc”,模式p=“abcdx”。结果应该返回5。 暴力匹配的图解如下: 代码如下: public clas...
  • kmp匹配算法

    2016-08-07 08:24:51
    KMP算法可在一个主“文本字符”S内查找一个“词”W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现,从而避免重新检查先前匹配的字符。 —
  • 1. 简单的模式匹配算法——BF模式匹配 的模式匹配,是求模式在主中的位置。时间复杂度 O(n*m). 下面来看一下代码 int Index(SString S, SString T, int pos){ int i = pos; int j = 1; while(i <= S....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,008
精华内容 12,803
关键字:

串的kmp匹配算法的算法过程