精华内容
下载资源
问答
  • 实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...
  • 这是重庆大学数据结构实验报告,题目是串的操作与KMP模式匹配算法。里面有完整的实验流程,包括源码及结果截屏
  • 字符串匹配算法:KMP、BM和Sunday

    一、暴力匹配

    	public static int worstMatch(String s, String p)  
    	{  
    	    int sLen = s.length();  
    	    int pLen = p.length();  
    	  
    	    int i = 0;  
    	    int j = 0;  
    	    while (i < sLen && j < pLen)  
    	    {  
    	        if (s.charAt(i) == p.charAt(j)) 
    	        {  
    	            //如果当前字符匹配成功(即S[i] == P[j]),则i++,j++      
    	            i++;  
    	            j++;  
    	        }  
    	        else  
    	        {  
    	            //如果失配(即S[i]! = P[j]),s回退j步到匹配开始的位置,
    	            //然后从下一位置重新开始,即i = i - j+1      
    	            i = i - j + 1;  
    	            j = 0;  
    	        }  
    	    }  
    	    //匹配成功,返回模式串p在文本串s中的位置,否则返回-1  
    	    if (j == pLen)  return i - j;  
    	    return -1;  
    	}
    

    二、KMP算法

    对于KMP算法,这篇博客讲解得非常透彻。KMP算法详解

    1、KMP思想

    总的思想:记录模式串中最长重复子串,只移动模式串,当发现不匹配字符时,模式串的指针尽可能少的回退到下一个可能匹配的位置。
    例如匹配串s是ABCDEABCDEABCDFABCDE,模式串p是ABCDEABCDF,那么模式串p中F之前实际上有最长重复子串ABCD,所以当指针i移到s[9],指针j移到p[9]时,发现字符E和字符F不相等,则i不变j回退到4,下次匹配时直接比较s[9]和p[4]即可,而无须i回到1,j回到0。即当s[i]和s[j]不匹配时,j=next[9]=4。
    那么如何得到next数组呢,假设已知next[i]=k,则p[0]、p[1]、p[2]、…、P[k-1]这前k个字符与p[i-k]、p[i-k+1]、p[i-k+2]、~、p[i-1]这后k个字符相同,那么计算next[i+1]时,我们只需要判断p[i]和p[k]两个字符就有可能确定next[i+1]的值。如果p[i]=p[k],依照next的定义即可知道next[i+1]=k+1。
    以ABEABCDABEABCD为例,我们知道next[12]=5,那么在求next[13]时,p[5]=C、p[12]=C、它们相等那么就可以直接确定next[13]=6。
    再看p[i]和p[k]不相等的情况,我们假设next[k]=j,那么第一段p[0]、…、p[j-1],第二段p[k-j]、…、p[k-1],第三段p[i-k]、…、p[i-k+j-1]以及第四段p[i-j]、…、p[i-1]这四段长度为j的字符串都是相同的。也就是说如果p[j]==p[i],那么p[0]、…、p[j]这前j+1个字符串与p[i-j]~p[i]这后j+1个字符串一定是相同的,也就是说next[i+1]=next[k]+1。
    以ABEABCDABEABED为例,我们知道next[12]=5,但是p[5]是C、p[12]是E,它们不相等所以不能得出next[13]=6,再看next[5]的值,它前面是ABEAB,所以next[5]=2,我们比较p[2]和p[12]的值发现它们相等,这个时候我们就可以得出next[13]=3。而若以ABEABCDABEABDC为例,因为next[12]=5,next[5]=2,但是此时p[2]!=p[12]且next[2]=0,则可以直接得出next[13]=0。

    2、KMP代码

    从上面的分析可以看出,在已知next[i]=k时,若p[i]=p[k],则next[i+1]=k+1。若p[i]!=p[k],则需要判断next[next[i]]的值,即若next[next[i]]=j,则判断一下p[j]和p[i]的值,若相等则next[i+1]=next[next[i]]+1。若不相等则需要继续判断直至next值为0。从编程的角度来看,我们判断p[i]的值是否能追加到之前的最长相同前后缀时,求的其实是next[i+1],也就是最外层循环只有n-1次,同时有可能存在一个内部循环。于是可以写出以下代码:

    	private static int[] getNext(String pattern){
    		if(pattern==null) return null;
    		int len=pattern.length();
    		if(len==0) return null;
    		int[] next=new int[len];
    		next[0]=-1;		
    		int k;
    		for(int i=0;i<len-1;i++){
    			k=next[i];
    			if(k==-1||pattern.charAt(i)==pattern.charAt(k)){
    				next[i+1]=k+1;
    			}else{
    				while(k>0){
    					if(pattern.charAt(i)==pattern.charAt(k)){
    						next[i+1]=k+1;
    						break;
    					}else{
    						k=next[k];
    					}
    					if(k<=0) next[i+1]=0;
    				}
    			}
    		}
    		return next;
    	}
    

    不过这段代码虽然逻辑上比较清晰但是不够简练,它可以优化成下面这段代码:

    	private static int[] getNext(String pattern){
    		if(pattern==null) return null;
    		int len=pattern.length();
    		if(len==0) return null;
    		int[] next=new int[len];
    		next[0]=-1;
    		int k=-1;
    		int i=0;
    		while(i<len-1){
    			if(k==-1||pattern.charAt(i)==pattern.charAt(k)){
    				next[++i]=++k;
    			}else{
    				k=next[k];
    			}
    		}
    		return next;
    	}
    

    那么完整的KMP代码就是:

    	public static int kmpSearch(String s, String p)  
    	{  
    		if(s==null) return -1;
    		if(p==null) return -2;
    		int sLen=s.length(),pLen=p.length();
    		if(sLen==0) return -1;
    		if(pLen==0) return -2;
    		int[] next=getNext(p);
    		int i=0,j=0;
    	    while (i < sLen && j < pLen)  
    	    {  
    	        //①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++      
    	        if (j == -1 || s.charAt(i) == p.charAt(j))  
    	        {  
    	            i++;  
    	            j++;  
    	        }  
    	        else  
    	        {  
    	            //②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]      
    	            //next[j]即为j所对应的next值        
    	            j = next[j];  
    	        }  
    	    }  
    	    if (j == pLen)  
    	        return i - j;  
    	    else  
    	        return -1;  
    	}
    

    3、next数组优化

    同时大神的博客也讲到了next数组的一个优化,假设匹配串ababbcabadabc、模式串ababbcabab。next数组不优化时为[-1,0,0,1,2,0,0,0,2,3],第一趟匹配失败发生在i=9,j=9。此时next[9]=3,所以第二趟匹配开始时i=9,j=3,而这必然是匹配失败的,因为s[9]=d,p[3]=b之前已经比较了d和b不相等,所以s[9]和p[3]的匹配完全是没必要的。同样next[3]=1,s[1]=b,也无需匹配。这种优化是很有必要的,因为next数组优化是一次性的,而模式串中有可能多次出现类似情况,如果在匹配时再去尝试这种必定失败的操作,会造成很大的不必要的性能开销。
    所以当匹配失败且p[next[j]]=p[j]时,需要循环回退到不与p[j]相同的next点。那么代码中需要再增加一个循环判断吗?实际上也并不需要,因为在求next数组时,是从前向后计算的,我们可以保证之前的每个p[next[k]]不等于p[k],那么如果某点i的前继为k且p[i]=p[k],则next[i]应为k的前继next[k],那么p[next[i]]=p[next[k]]不等于p[k]即不等于p[i]。
    因此代码中实际上只须回退一次就够了,没必要循环回退,改进的代码如下

    	private static int[] getNext(String pattern){
    		if(pattern==null) return null;
    		int len=pattern.length();
    		if(len==0) return null;
    		int[] next=new int[len];
    		next[0]=-1;
    		int k=-1;
    		int i=0;
    		while(i<len-1){
    			if(k==-1||pattern.charAt(i)==pattern.charAt(k)){
    				i++;
    				k++;
    				//优化next数组
    				if(pattern.charAt(i)==pattern.charAt(k)){
    					next[i]=next[k];
    				}else{
    					next[i]=k;
    				}
    			}else{
    				k=next[k];
    			}
    		}
    		return next;
    	}
    

    三、BM算法

    BM算法的核心思想是后向匹配,坏字符和好后缀规则。
    三步引入BM算法
    BM算法详解

    1、后向匹配

    KMP算法中,都是从匹配串S和模式串P的起始位置开始匹配,模式串P的指针是从左向右移动。而BM算法是后向匹配,模式串P的指针是从右向左移动。当然匹配串S的指针肯定仍然是从左向右移动。
    实际上对于长度为n的匹配串S和长度为m的模式串P,即使是用暴力匹配法也最多只需要匹配n-m+1次,每次需要比较两个长度为m的字符串是否匹配,发现当前子串不匹配时将匹配串的起始指针整体右移一位,即进行另一次匹配。而BM算法的目标就是尽量增大这个步长,每次匹配失败之后尽可能移动多位。

    	public static int reverseMatch(String s, String p)  
    	{  
    	    int sLen = s.length();  
    	    int pLen = p.length();  
    	    int iStart = pLen-1;
    	    int i=iStart;  
    	    int j = pLen-1;  
    	    while (j>=0&&iStart<=sLen-1)  
    	    {  
    	        if (s.charAt(i) == p.charAt(j))  {  
    	            //如果当前字符匹配成功,则指针从后往左移动一位    
    	            i--;  
    	            j--;  
    	        }  else  {  
    	            //如果存在不同字符,则开始下一次匹配,iStart只移动了一位
    	            iStart = iStart+1;
    	            i=iStart;  
    	            j = pLen-1;  
    	        }  
    	    }  
    	    //匹配成功,返回模式串p在文本串s中的位置,否则返回-1  
    	    if (j == -1)  return iStart - pLen+1;  
    	    return -1;  
    	}
    

    2、坏字符

    【待完成】

    3、好后缀

    【待完成】

    四、Sunday算法

    【待完成】Sunday算法介绍

    五、RK算法

    【待完成】基于Hash思想的RK算法

    展开全文
  • 模式匹配数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出该字串相同的所有子串,这就是模式匹配。其中原字符串成为目标串,给定的子串为模式串。通俗理解如下图1-1: 二、常用的模式...

    一、模式匹配的概念

    模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出该字串相同的所有子串,这就是模式匹配。其中原字符串成为目标串,给定的子串为模式串。通俗理解如下图1-1:


    二、常用的模式匹配算法

    1、朴素的模式匹配算法(也称简单匹配算法,Brute-Force简称BF算法)

    A.算法思想:

    核心是穷举法。从目标串的的第一个字符起与模式串的第一个字符比较,若相等,则继续对字符进行后续的比较,否则目标串从第二个字符起与模式串的第一个字符重新比较,直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止,此时称为匹配成功,否则匹配失败。

    B.算法演示(给定目标串goodgoogle,模式串google)

    C.代码实现

    #include <iostream>
    #include <string>
    using namespace std;
    
    int Match1(string str, string searchStr)
    {
    	int i = 0;
    	int j = 0;
    	while (i < str.size() && j < searchStr.size())
    	{
    		if (str[i] == searchStr[j])
    		{
    			i++;
    			j++;
    		}
    		else//指针回退,重新开始匹配
    		{
    			i = i - j + 1;//目标串回到匹配位置的下一位置
    			j = 0;//模式串回到起始0位置
    		}
    	}
    	if (j >= searchStr.size())
    	{
    		return i - searchStr.size();//返回第一次匹配的首地址
    	}
    	else
    	{
    		return -1;
    	}
    }
    int main(){
    	string s = "goodgoogle";
    	string t = "google";
    	cout << Match1(s, t)<<endl;
    }

    D.算法分析

    设目标串s的长度为n,模式串t的长度为m

    最好情况下的时间复杂度O(m);

    最差情况下的时间复杂度O(n*m);

    平均时间复杂度O(n*m)。


    2、KMP匹配算法

    Knuth-Morris-Pratt算法(简称KMP),是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法,消除了朴素的模式匹配算法中回溯问题,完成串的模式匹配。

    A.算法思想:

    设目标串为s,模式串为t, i、j 分别为指示s和t的指针,i、j的初值均为0。

    若有 si = tj,则i和j分别增1;否则,i不变,j退回至j=next[j]的位置 ( 也可理解为串s不动,模式串t向右移动到si与tnext[j]对齐 );

    比较si和tj。若相等则指针各增1;否则 j 再退回到下一个j=next[j]的位置(即模式串继续向右移动 ),再比较 si和tj。

    依次类推,直到下列两种情况之一:

    1)j退回到某个j=next[j]时有 si = tj,则指针各增1,继续匹配;

    2)j退回至 j=-1,此时令指针各增l,即下一次比较 si+1和 t0

    B.算法演示

     C.代码实现

    #include<iostream>
    #include<string>
    using namespace std;
     
    //计算子串的next数组
    void get_next(string t, int *next)
    {
    	int i, j;
    	i = 1;
    	j = 0;
    	next[1] = 0;
    	while (i<t.size() - 1)
    	{
    		if (j == 0 || t[i] == t[j])//t[i]表示后缀的单个字符,t[j]表示前缀的单个字符
    		{
    			i++;
    			j++;
    			next[i] = j;
    		}
    		else
    			j = next[j];			//若字符不相同,则j值回溯
    	}
     
    }
     
    //返回子串t在主串t中第pos个字符之后的位置;若不存在,函数返回0
    //s[0]和t[0]应该保存字符串的长度,这里我们随意保存一个字符#
     
    int KMP(string s, string t)	        //默认从主串的第一个位置开始查找
    {
    	int i = 0;					//i用于表示主串s的当前位置
    	int j = 0;					//j用于表示子串t的当前位置
    	int next[255];					//定义一个next数组
    	get_next(t, next);				//对串做分析,得到next数组
    	while (i < s.size() && j < t.size())		//若i小于s的长度且j小于t的长度,循环继续
    	{
    		if (j == 0 || s[i] == t[j])		//两字符串相等,或j处于开始位,继续
    		{
    			i++;
    			j++;
    		}
    		else					//j值退回合适的位置,i值不变
    			j = next[j];
    	}
    	if (j >= t.size())
    		return i - t.size();
    	else
    		return 0;
    }
     
    int main()
    {
    	string s = "#goodgoogle";
    	string t = "#google";
    	cout << KMP(s, t) << endl;
    	return 0;
    }

    D.算法分析

    对于长度为m的模式s和长度为n的目标t的模式匹配,KMP算法的时间复杂度为O(m+n)。

    展开全文
  • C/C++实现串匹配算法,包括源代码和实验报告。实现了串的创建,查看,修改,朴素的模式匹配算法,kmp算法和kmp改进算法。
  • 主要介绍了Java数据结构算法实例:朴素字符匹配 Brute Force,本文直接给出实例代码,代码中包含详细注释,需要的朋友可以参考下
  • 图解数据结构算法

    万人学习 2020-07-27 10:56:16
    【为什么学习数据结构算法】     程序=数据结构+算法数据结构算法是程序的基础,没有系统地学习过数据结构算法的程序员只能称作是coder,知道我们写的代码使用了什么数据结构,它的特征是什么。...
  • 编程实现如下功能: 1、在实验六的基础上,实现串的Brute-Force模式匹配算法。 2、尝试实现串的KMP模式匹配算法
  • 数据结构---串的模式匹配算法介绍

    万次阅读 多人点赞 2017-02-21 19:26:05
    前言 The years teach much which the days never knew. Time:2017/2/19 Name:Willam 1、介绍 对于文本程序来说,找出一个子串在文本中的位置是特别重要的,...2、实现算法(1)—朴素字符串匹配算法 原理:从

    前言
    The years teach much which the days never knew.
    Time:2017/2/19
    Name:Willam

    1、介绍
    对于文本程序来说,找出一个子串在文本中的位置是特别重要的,我们称那个子串为模式串(pattern),然后我们称寻找的过程为:模式匹配(string match)。

    2、实现算法(1)—朴素字符串匹配算法

    原理:从主串的指定的起始位置字符开始和模式第一个字符比较,如果相等,则继续比较下一个字符,如果不等,则从主串的下一个字符开始和模式的第一个字符开始比较,以此类推,直到模式串所有字符都匹配完成,则匹配成功,否则,匹配不成功。

    代码实现

    
    //pos是从1开始的一个下标
    int index_force(char * s, char * t,int pos)
    {
    
        int i=pos-1;
        //判断pos是否合法
        if(!s[i])
        cout<<"起始位置不合法"<<endl;
        int j=0;
        while(s[i]!='\0' && t[j]!='\0')//主串或者模式串遍历完成
        {
            if(s[i]==t[j])//如果主串和模式串对应位置的值相等,则比较后面的字符
            {
                ++i;
                ++j;
            }
            else    //如果不相等,则模式串需要回朔到第一个字符,而主串则从下一个字符开始
            {
                i=i-j+1;
                j=0;
            }
        }
        if(t[j]=='\0')//如果循环是由于模式串遍历完了而结束的,说明找到了对应子串的位置
        {
            return i-j+1;
        }
        else        //否则,主串不包含模式串
        {
            return 0;
        }
    }
    

    时间复杂度的分析:我们这里只分析最坏的情况,那就是对于长度为n的模式串和长度为m的主串,模式串前n-1都是同样的字符而且主串的前m-1也是和模式串一样的字符,例如:模式串为:000001,主串为:000000000000000000000001,则对于这种情况的时间复杂度为:其中我们需要回朔:m-n+1次,每次都要比较:n次,所以我们的时间复杂度为:o((m-n+1)n)

    3、实现算法(2)—-KMP算法的实现
    简介:KMP算法它是有Knuth、Morris和Pratt三个人同时发现的,所以我们称之为KMP算法。它是一个很优秀的算法,通过对模式串的一个预处理,将我们的时间复杂度减少到了一个线性的水平。

    剖析算法的原理:
    下面我们将在实际的应用中来解释这个算法,首先我们有主串:acabaabaabcacaabc,有模式串:abaabcac,现在假设我们匹配到了如下的图的步骤:
    这里写图片描述
    现在模式串的第六个字符和主串匹配不上了,那么现在我们就需要把模式串往右移动,并且重新选择主串和模式串的比较位置重新开始比较。那么如果是朴素法的话,我们是直接把模式串往右移动一格,然后,主串的第四个字符和我们模式串的第一个字符重新开始做比较。但是,你要知道其实主串的第三个字符到第六个字符我们都是已经和模式串做过比较的,而且我们知道他们的各个位置上的内容是什么,那么为什么不把这些已经知道的信息充分利用起来了?比如:我们知道模式串中红色的两个字符和绿色的两个字符是相等的,而且红色的两个字符正好是模式串开始的两个字符,所以我们可以直接把模式串向右移动四位,然后,我们主串从刚才发现不匹配那个字符位置开始和模式串的第三个位置比较,这样我们就可以减少五次比较。
    哇噻,就是一个简单的处理,就给我们的程序效率带来了质的飞越,那么现在程序的最要紧要解决的问题就是我们主串比较位置不做任何改动,那么我们怎么知道该从模式串的哪个位置开始做比较了,这个时候,我们就需要对我们的模式串做一个预处理,通过预处理我们可得到一个next数组,它保存的就是当我们在模式串某个位置匹配失败后,应该从模式串的哪个位置重新开始比较。要求得next数组,那么我们就要理解刚才的那个例子为什么可以从模式串的第三个位置重新开始比较。其实next数组就是说对于模式串j这个位置之前(1到j-1)的串中,是否存在从模式串第一个位置出发往右移动得到的子串从模式串的第j-1个字符位置出发往左移动得到的子串匹配,而且当该串达到最大长度时,则next值就是该串的长度加一,例如:abaabc这个模式串中,在c这个位置之前存在一个最大子串:ab。然后,我们next值就是记录这个最大子串的下一个字符的位置,其实说到这里,我们也就理解到了为什么要第三个字符了,因为模式串的前两个字符已经和主串匹配成功了(生成next值的时候,就完成了这个任务),所以不用再比较了。
    代码实现:
    get_next函数的实现

    //next函数的实现,
    void get_next(char * s,int * next)
    {
        int i=0;  //next数组的下标
        int j=-1;  //next值
        next[0]=-1;
        while(s[i]!='\0')
        {
            if(j==-1 || s[i]==s[j]) //如果不存在或这条件符合了,那么就可以得到next值了
            {
                ++i;++j;
                next[i]=j;
            }
            else{
                j=next[j];
            }
        }
    }

    KMP函数的实现:

    //KMP算法的实现
    int KMP(char * s,char * t,int pos)
    {
    
        int j=0;
        while(t[j++]!='\0');
        int * next=new int[j-1];
    
        int length=j-1; //串的长度
        //调用函数,生成对应的next值
        get_next(t,next);
    
        int i=pos-1;//主串的起始位置
        j=0;//模式串的下标
        while(s[i]!='\0' && j<length)
        {
            if(j==-1 || s[i]==t[j]) //考虑到第一个不相等的情况
            {
                ++i;++j;
            }
            else
            {
                j=next[j];  //如果不相等,则从next值开始下一次比较(模式串的右移)
            }
        }
    
        if(t[j]=='\0' && j!=-1)
        {
            return i-j+1;
        }
        else
        {
            return 0;
        }
    }
    

    算法的改进:
    其实我们的next函数还是有一点缺陷,我们还可以通过一定的改进,让我们的算法的得到进一步的优化,例如:当我们的模式串为:ooooa,主串为:ooocooooa,我们根据之前的next函数可以得到next数组的值为:-10123,所以当我们的模式串的第四个字符和主串的第四个字符发生不相等的时候,我们还需要额外的三次比较,才知道这个我们应该直接把主串往前移动一位,后继续比较。其实,我们完全可以在生成next值的时候,避免这种情况出现,代码修改如下:

    //next函数的实现,
    void get_next(char * s,int * next)
    {
        int i=0;  //next数组的下标
        int j=-1;  //nextnext[0]=-1;
        while(s[i]!='\0')
        {
            if(j==-1 || s[i]==s[j]) //如果不存在或这条件符合了,那么就可以得到next值了
            {
                ++i;++j;
                //修改代码部分
                if(s[i]!=s[j])//只有两者不相等的时候,才需要更换nextnext[i]=j;
                else
                next[i]=next[j];
            }
            else{
                j=next[j];
            }
        }
    }

    时间复杂度的分析:KMP算法就有两个步骤:第一个就是花费:O(m)的时间去对模式串进行预处理,其中m为模式串的长度,另外一个就是遍历主串,最坏的情况就是:O(n),其中n为主串的长度,所以KMP的时间复杂度为:O(m+n)

    4、实现算法(4)—Horspool算法
    简介:Horspool算法是一个基于后缀匹配的一种模式匹配算法,它算是匹配算法中的一种的新的创新,因为我们在匹配模式串的时候,都是从左向右匹配的,但是Horspool却是从右向左匹配,其实它的这种思路我们也是知道的:那就为了让模式串可以尽可能的向右移动的距离长一点,这样我们的匹配算法的效率才会提高,那么后缀匹配的方法到底有什么好处了,通过下面这幅图,你就明白了
    这里写图片描述
    我们如果从模式串的最后一个字符开始比较,那么当第一个字符不可以的时候,我们可以马上停止比较其他字符,从而节省多次比较。当然,我们怎么知道我们需要把模式串往右移动多少位了,那么这个正是Horspool算法要做的事情

    算法原理的剖析
    模式串从右向左进行匹配。对于每个文本搜索窗口(其实就是主串中一个和模式串长度相等的子串,我们称之位一个文本搜索窗口),将窗口内的最后一个字符与模式串的最后一个字符进行比较。如果相等,则继续从后向前验证其他字符,直到完全相等或者某个字符不匹配。然后,无论匹配与否,都将根据在模式串的下一个出现位置将窗口向右移动。模式串与文本串口匹配时,模式串的整体挪动,是从左往右,但是,每次挪动后,从模式串的最后一个字符从右往左进行匹配。,算法的解释可能太过抽象,那么下面我们直接看一个示例:其中我们的主串是:abcbcsdcodecbcac,模式串是:cbcac

    模拟Horspool算法模式匹配的过程:
    (1)第一步
    这里写图片描述
    首先,我们从对主串和模式串从左向右进行匹配,发现模式串的第四个字符(a)和主串的字符(b)不匹配,那么这个时候我们就要移动模式串,我们需要从模式串的右边向左寻找。模式串是否有字符(b),我们就在模式串的第二个位置找到了,所以我们就需要把模式串的b和主串上的b对齐,换句话说,就是模式串需要往右移动两位(3-1,其中3是不匹配时,模式串中字符的下标,另外一个就是b在模式串中的下标,下标是从0开始)

    (2)第二步
    这里写图片描述
    现在,我们继续从右向左比较模式串和主串的值,然后,我们发现第一个字符就不匹配了,其中,主串不匹配的字符为:d,然后,从右向左在模式串中寻找d,最后发现,模式串中没有d,那么我们直接把模式串整体往右移动到其第一个字符和主串刚刚那个不匹配字符d的下一个字符(c)对齐,其中,模式串整体往右移动了5个位置(4-(-1)=5,其中4是模式串不匹配时,模式串值中那个字符的下标,因为d不存在于模式串中,所以我们寻找到的下标为:-1)

    (3)第三步
    这里写图片描述
    我们重复第二步的步骤,因为e同样不在模式串中。
    (4)第四步
    这里写图片描述
    好了,经过了四个步骤,我们终于匹配成功,通过了这个例子我们应该已经知道了Horspool算法的原理了,并且代码实现,应该也很容易了。
    我们得到的规则只有一条,即:

                        **字符串后移位数=失配字符位置-失配字符上一次出现的位置**
    

    如果失配字符根本就没有出现在模式串中,我们将“失配字符上一次出现的位置”的值视为-1。

    代码实现:

    //Horspool函数的实现
    int Horspool(char * source,char * pattern)
    {
        int source_length=strlen(source);
        int pattern_length=strlen(pattern);
        int i=0;    //主串的下标的移动
        int j=0;    //模式串的下标
        int k=0;     
        char misch;  //记录未匹配成功时,主串上的字符
        int mis_dis=0;
        for(i=0;i<=source_length-pattern_length;)//注意终止条件,就是当剩余的串已经不够长时,就可以终止了
        {
            for(j=pattern_length-1;j>=0;--j)
            {
                if(source[i+j]!=pattern[j])
                {
                    misch=source[i+j];
                    mis_dis=j;
                    break;          
                }
                if(j==0)
                return i+1;
            }
            //寻找模式串中是否有未匹配的字符
            for(k=mis_dis-1;k>=0;--k)
            {
                if(pattern[k]==misch)
                {
                    i+=(mis_dis-k);
                    cout<<"i="<<i<<endl;break;
                }       
                  if(k==0)//不存在的时候
                {
                    i+=(mis_dis+1);
                    cout<<"i="<<i<<endl;
                }
            }
        }
        return 0;
    
    }   

    5、实现算法(3)—-BM算法

    简介:BM算法是在1977年由Robert S.Boyer和J Strother Moore提出的一个基于后缀匹配的模式匹配算法,它的匹配速度比KMP都还快4-5倍,而且在绝大多数的场合下的应用性能极嘉,比如我们经常使用的Ctrl+F就是通过这个算法实现模式匹配的。

    算法原理的剖析

    BM算法性能之所以可以比KMP算法好,第一个原因就是它使用了后缀匹配的模式匹配算法(这里在Horspool里解释了原因),另外,一个就是它对当模式串出现不匹配的情况时,采取两种方式并行移动模式串的算法,其中一种叫:坏字符规则,还有一种叫做:好后缀规则。

    好了,在介绍什么是坏字符规则和好后缀规则之前,我们先来看看什么是坏字符和好后缀。如下图所示:
    这里写图片描述

    如上图,第一行就是主串,第二行为模式串,当模式串匹配到红线的时候,发现和主串的字符不匹配了,那么主串的字符:“I”,就是坏字符,而模式串的字符串:“MPLE ”,这个字符串我们叫好后缀。

    开心,现在我们都明白什么是坏字符和好后缀了。下面我就先给大家介绍什么是坏字符规则。其实,我们所说的规则都是在模式匹配失败的时候,计算我们模式串需要移动的距离,这样我们才可以在一个新的位置重新进行模式匹配,在坏字符规则下,模式串移动有两种情况:

    • 坏字符没出现在模式串中,这时可以把模式串移动到坏字符的下一个字符,继续比较,如下图:
      这里写图片描述
    • 坏字符出现在模式串中,这时可以把模式串最右边第一个出现的坏字符和主串的坏字符对齐,当然,这样可能造成模式串倒退移动(这个情况的出现也是我们需要好后缀规则的一个原因),如下图:
      这里写图片描述

    好了,到这里我们可以先用代码把坏字符规则实现,其实,我们先按照ASCII编码的规则,来实现我们的坏字符,因为,我们从上面的两种情况可以知道,其实如果某个字符不在模式串中,那么这个时候,模式串需要往右移动距离为模式串的长度,所以我们可以声明一个大小为256的数组,记录每个ASCII值在字符不匹配时,坏字符时该ASCII值时,模式串需要移动的距离。

    /*//Bc函数的实现,因为我们是按照ASCII编码规则进行代码设计的,所以我们开始就申请256个空间
    //  第一个for循环处理上述的第一种情况,这种情况比较容易理解就不多提了。
    //  第二个for循环,Bc_table[s[j]中s[i]表示模式串中的第i个字符。
    //  Bc_table[s[j]]=len-j-1;也就是计算s[i]这个字符到串尾部的距离。
    //  为什么第二个for循环中,i从小到大的顺序计算呢?哈哈,技巧就在这儿了,原因在于就可以在同一字符多次出现的时候以最靠右的那个字符到尾部距离为最终的距离。当然了,如果没在模式串中出现的字符,其距离就是len了。
    */
    void Bc(char * s,int * Bc_table)
    {
        int len=strlen(s);
        int i=0;
        for(i=0;i<256;i++)
        {
            *(Bc_table+i)=len;  //先把映射表的距离全部初始化为模式串的长度
        }
        int j=0;
        for(j=0;j<len-1;++j)
        {
            Bc_table[s[j]]=len-j-1;//记录模式串中,每个字符最靠右那个字符的位置
        }
    }

    下面,我们再看看什么是好后缀规则,好的后缀规则同样是会有三种情况出现:

    • 模式串中有子串匹配上好后缀,此时移动模式串,让该子串和好后缀对齐即可,如果超过一个子串匹配上好后缀,则选择最靠左边的子串对齐。
      这里写图片描述
    • 模式串中没有子串匹配上后后缀,此时需要寻找模式串的一个最长前缀,并让该前缀等于好后缀的后缀,寻找到该前缀后,让该前缀和好后缀对齐即可。
      这里写图片描述
    • 模式串中没有子串匹配上后后缀,并且在模式串中找不到最长前缀,让该前缀等于好后缀的后缀。此时,直接移动模式到好后缀的下一个字符。
      这里写图片描述

    通过,上述的三种情况,为了实现好后缀规则,需要定义一个数组suffix[],其中suffix[i] = reslut 表示以i为边界,与模式串后缀匹配的最大长度,如下图所示,用公式可以描述:满足P[i-s, i] == P[len-result, len]的最大长度reslut。记住:我们需要匹配的是模式串的后缀表达式,所以每次得到了模式串某个位置的最长后缀表达式的长度之后,下一个位置又是和我们的模式串的最后一个字符开始比较。

    下面就是我们得到suffix数组的函数

    void get_suffix(char * s,int * suffix)
    {
        int i=0;
        int j=0;
        int k=0;
        int result;
        int len=strlen(s);  //模式串的长度
        suffix[len-1]=len;  //模式串最后一个字符是一个特例,它是一个完全模式串后缀,所以长度就是模式串的长度
        for(i=len-2;i>=0;--i)  //从模式串的倒数第二个字符开始循环,求suffix的值
        {
            k=i;   //我们想要寻找的那个子串的第一个字符
            j=len-1; //模式串的最后一个字符
            result=0; //记录那个子串的长度
            while(s[k--]==s[j--]) //开始往前比较
            {
                ++result;
            }
            suffix[i]=result; //得到最大模式串的后缀的长度
        }
    }
    

    好了,现在有了suffix,我们就要开始进行我们的好后缀规则的实现了,其实,它同样是得到一个数组,这个数组记录每次我们遇到了不匹配字符时,在该字符所在的位置上,以好后缀的规则,模式串需要移动的距离。在生成这个距离的时候,我们我们同样是要对好后缀可能出现的三种情况进行考虑,

    • 模式串中没有子串匹配上好后缀,但找不到一个最大前缀
      这个时候,模式串需要移动的距离就是模式串的长度,这也是我们默认的移动距离,所以,程序一开始就可以把数组初始化为模式串的长度

    • 模式串中没有子串匹配上好后缀,但找到一个最大前缀
      这里写图片描述

    • 模式串中有子串匹配上好后缀
      这里写图片描述

    通过,这里分析的三种情况,我们可以编写出如下代码:

    //Gs映射表的求解函数,
    void Gs(char *s ,int * Gs_table)
    {
        int len= strlen(s);
        int i;
        int * suffix=new int[len];
        //生成suffix数组
        get_suffix(s,suffix);
        for(i=0;i<len;i++)
        {
            Gs_table[i]=len;  //先把所有的移动距离初始化为模式串的长度
        }
        int j=0;
        //第二种情况
        for(i=len-2;i>=0;--i)
        {
            if(suffix[i]==i+1)//x[i+1-suff[i]…i]==x[m-1-siff[i]…m-1],而suff[i]==i+1,我们知道x[i+1-suff[i]…i]=x[0,i],也就是前缀,满足第二种情况。
            {
                for(;j<len-1-i;++j)  //
                {
                    if(Gs_table[j]==len)//保证只被修改一次
                    {
                        Gs_table[j]=len-1-i;
                    }
                }
            }
        }
        for(i=0;i<=len-2;++i)   //对应于第三种情况,结合着前面图来理解代码
            Gs_table[len-1-suffix[i]]=len-1-i;
    }
    

    在这里,仔细去分析和感受一下,Gs函数的编写是有很多技巧在里面的,首先我们要先有个概念就是:当我们按照好后缀规则移动的时候,如果模式串的一个字符位置同时符合刚刚分析的三种情况中的几种,所以我们要选择其中移动距离最小的那一种,这样才可以保证不会出现匹配遗漏,通过分析,我们发现上述的三种情况中,其中第一种情况的移动距离最大,所以最先考虑,第二种为第二,第三种移动距离最小。
    我们先是假设模式串每个字符都是符合第一种情况,就是没有最大前缀也没有匹配的模式串后缀,其实就是把整个数组初始化为模式串的长度。然后,我们再考虑第二种情况,我们从下面几个问题来分析第二种情况
    1. 为什么从后往前,也就是i从大到小?     
    原因在于如果i,j(i>j)位置同时满足第二种情况,那么m-1-i

    int BM(char * s,char * t)
    {
        int i=0;
        int j=0;
        int length_s=strlen(s);  //主串的长度
        int length_t=strlen(t);  //模式串的长度
        int * B=new int[256];
        int * G=new int[length_t];
        Bc(t,B);
        Gs(t,G);
        while(j<=length_s-length_t)
        {
            for(i=length_t-1;i>=0 && s[i+j]==t[i];--i);//往前匹配
            if(i<0)
            {   
                return j+1;
            }
            else
            {
                int g=G[i];
                int b=B[s[i+j]]-length_t+1+i;
                //选择最大的值
                if(g>=b)
                    j+=g;
                else
                    j+=b;
    
            }
        }
        return 0;
    }
    

    好了,到现在,BM算法实现完成。

    6、总结
    哎哎,本来昨晚就写好的了,但是今天由于CSDN的bug,让我的博客变的不完整,从BM算法那里,我又重新写了一遍,算是因祸得福吧,通过这次的编写,我发现我对BM算法的原理更加明清了,打算,去看看原论文,看看是不是和我的理解一样。

    参考博客:
    http://www.cnblogs.com/xubenben/p/3359364.html

    论文下载:
    http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

    展开全文
  • #资源达人分享计划#
  • //match.h #include <malloc.h> //malloc,realloc #include <math.h> //overflow #include <process.h> //exit() #include #define S_SIZE 100 //栈的空间大小 #define STACKINCREAMENT 10/... //文本括号匹配 };
  • C++模板实现的数据结构字符串类,实现了字符串的拼接、删除、截取、转换、匹配、替换等常用功能,其中匹配算法使用了基于KMP的快速匹配算法。程序具有良好的编码风格和详细的算法注释。
  • 数据结构KMP算法配图详解(超详细)

    万次阅读 多人点赞 2020-02-18 22:02:42
    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...

    KMP算法配图详解

    前言

    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂,很多正规的书本把概念一摆出直接劝退无数人。这篇文章将尽量以最详细的方式配图介绍KMP算法及其改进。文章的开始我先对KMP算法的三位创始人Knuth,Morris,Pratt致敬,懂得这个算法的流程后你真的不得不佩服他们的聪明才智。

    KMP解决的问题类型

    KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配。比如主串s=“goodgoogle”,子串t=“google”。现在我们要找到子串t 在主串s 中的位置。大家肯定觉得这还不简单,不就在第五个嘛,一眼就看出来了。
    当然,在字符串非常少时,“肉眼观察法”不失为一个好方法。但如果要你在一千行文本里找一个单词,我想一般人都会数得崩溃吧。这就让我想起来考试的时候,如果一两道选择题不会。这时候,“肉眼观察法”可能效果不错,但是如果好几道大题不会呢?“肉眼观察法”就丝毫不起效了。所以打铁还需自身硬,我们把这种枯燥的事以一定的算法交给计算机处理。
    第一种我们容易想到的就是暴力求解法。
    这种方法也叫朴素的模式匹配

    简单来说就是:从主串s 和子串t 的第一个字符开始,将两字符串的字符一一比对,如果出现某个字符不匹配,主串回溯到第二个字符,子串回溯到第一个字符再进行一一比对。如果出现某个字符不匹配,主串回溯到第三个字符,子串回溯到第一个字符再进行一一比对…一直到子串字符全部匹配成功。

    下面我们通过图片展示这个过程:
    竖直线表示相等,闪电线表示不等
    第一个过程:子串“goo”部分与主串相等,'g’不等,结束比对,进行回溯。
    在这里插入图片描述
    第二个过程:开始时就不匹配,直接回溯
    在这里插入图片描述
    第三个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第四个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第五个过程:匹配成功
    在这里插入图片描述
    大家可能会想:这个方法也太慢了吧!求一个子串位置需要太多的步骤。而且很多步骤根本不必要进行。
    这个想法非常好!!很多伟大的思想都是在一步步完善更正已有方法中诞生的。这种算法在最好情况下时间复杂度为O(n)。即子串的n个字符正好等于主串的前n个字符,而最坏的情况下时间复杂度为O(m*n)。相比而言这种算法空间复杂度为O(1),即不消耗空间而消耗时间。

    下面就开始进入我们的正题:KMP算法是怎样优化这些步骤的。其实KMP的主要思想是:“空间换时间”。
    大家打起精神,认真看下面的内容
    首先,为什么朴素的模式匹配这么慢呢?
    你再回头看一遍就会发现,哦,原来是回溯的步骤太多了。所以我们应该尽量减少回溯的次数。
    怎样做呢?比如上面第一个图:当字符’d’与’g’不匹配,我们保持主串的指向不变,
    主串依然指向’d’,而把子串进行回溯,让’d’与子串中’g’之前的字符再进行比对。
    如果字符匹配,则主串和子串字符同时右移。
    至于子串回溯到哪个字符,这个问题我们先放一放。

    我先提出一个概念:一个字符串最长相等前缀和后缀。
    教科书常用的手段是:在此处摆出一堆数学公式让大家自行理解。
    在这里插入图片描述
    这也是为什么看计算机学科的书没有较好的数学基础会很痛苦。(当初我为什么不好好学数学T_T)
    大家先不要强行理解数学公式,且听我慢慢道来:
    我给大家个例子。
    字符串 abcdab
    前缀的集合:{a,ab,abc,abcd,abcda}
    后缀的集合:{b,ab,dab,cdab,bcdab}
    那么最长相等前后缀不就是ab嘛.

    做个小练习吧:
    字符串:abcabfabcab中最长相等前后缀是什么呢:
    对就是abcab
    好了我们现在会求一个字符串的前缀,后缀以及最长相等前后缀了。
    这个概念很重要。到这里如果都看懂了,可以鼓励一下自己,然后回想一遍,再往下看。
    之前留了一个问题,子串回溯到哪个字符,现在可以着手解决了。

    图解KMP

    现在我们先看一个图:第一个长条代表主串,第二个长条代表子串。红色部分代表两串中已匹配的部分,
    绿色和蓝色部分分别代表主串和子串中不匹配的字符。
    再具体一些:这个图代表主串"abcabeabcabcmn"和子串"abcabcmn"。
    在这里插入图片描述
    在这里插入图片描述
    现在发现了不匹配的地方,根据KMP的思想我们要将子串向后移动,现在解决要移动多少的问题。
    之前提到的最长相等前后缀的概念有用处了。因为红色部分也会有最长相等前后缀。如下图:
    在这里插入图片描述
    在这里插入图片描述
    灰色部分就是红色部分字符串的最长相等前后缀,我们子串移动的结果就是让子串的红色部分最长相等前缀和主串红色部分最长相等后缀对齐。
    在这里插入图片描述
    在这里插入图片描述
    这一步弄懂了,KMP算法的精髓就差不多掌握了。接下来的流程就是一个循环过程了。事实上,每一个字符前的字符串都有最长相等前后缀,而且最长相等前后缀的长度是我们移位的关键,所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。
    所以next[i]=j,含义是:下标为i 的字符前的字符串最长相等前后缀的长度为j。
    我们可以算出,子串t= "abcabcmn"的next数组为next[0]=-1(前面没有字符串单独处理)
    next[1]=0;next[2]=0;next[3]=0;next[4]=1;next[5]=2;next[6]=3;next[7]=0;

    abcabcmn
    next[0]next[1]next[2]next[3]next[4]next[5]next[6]next[7]
    -10001230

    本例中的蓝色c处出现了不匹配(是s[5]!=t[5]),
    在这里插入图片描述
    我们把子串移动,也就是让s[5]与t[5]前面字符串的最长相等前缀后一个字符再比较,而该字符的位置就是t[?],很明显这里的?是2,就是不匹配的字符前的字符串 最长相等前后缀的长度。
    在这里插入图片描述
    也是不匹配的字符处的next数组next[5]应该保存的值,也是子串回溯后应该对应的字符的下标。 所以?=next[5]=2。接下来就是比对是s[5]和t[next[5]]的字符。这里也是最奇妙的地方,也是为什么KMP算法的代码可以那么简洁优雅的关键。
    我们可以总结一下,next数组作用有两个:
    一是之前提到的,

    next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

    二是:

    表示该处字符不匹配时应该回溯到的字符的下标

    next有这两个作用的源头是:之前提到的字符串的最长相等前后缀
    想一想是不是觉得这个算法好厉害,从而不得不由衷佩服KMP算法的创始人们。

    KMP算法的时间复杂度

    现在我们分析一下KMP算法的时间复杂度:
    KMP算法中多了一个求数组的过程,多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m),因后面匹配中主串不回溯,比较次数可记为n,所以KMP算法的总时间复杂度为O(m+n),空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n),KMP算法提速是非常大的,这一点点空间消耗换得极高的时间提速是非常有意义的,这种思想也是很重要的。
    下面还有更厉害的,我们一起来分析具体的代码。

    求next数组的代码

    下面我们一起来欣赏计算机如何求得next数组的

    typedef struct
    {	
    	char data[MaxSize];
    	int length;			//串长
    } SqString;
    //SqString 是串的数据结构
    //typedef重命名结构体变量,可以用SqString t定义一个结构体。
    void GetNext(SqString t,int next[])		//由模式串t求出next值
    {
    	int j,k;
    	j=0;k=-1;
    	next[0]=-1;//第一个字符前无字符串,给值-1
    	while (j<t.length-1) 
    	//因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
    	//所以最后一次经过while循环时j为t.length-2
    	{	
    		if (k==-1 || t.data[j]==t.data[k]) 	//k为-1或比较的字符相等时
    		{	
    			j++;k++;
    			next[j]=k;
    			//对应字符匹配情况下,s与t指向同步后移
    			//通过字符串"aaaaab"求next数组过程想一下这一步的意义
    			//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
           	}
           	else
    		{
    			k=next[k];
    			**//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
    			//也表示该处字符不匹配时应该回溯到的字符的下标
    			//这个值给k后又进行while循环判断,此时t.data[k]即指最长相等前缀后一个字符**
    			//为什么要回退此处进行比较,我们往下接着看。其实原理和上面介绍的KMP原理差不多
    			//printf("(2) k=%d\n",k);
    		}
    	}
    }
    

    解释next数组构造过程中的回溯问题

    大家来看下面的图:
    下面的长条代表子串,红色部分代表当前匹配上的最长相等前后缀,蓝色部分代表t.data[j]。
    在这里插入图片描述在这里插入图片描述

    KMP算法代码解释

    int KMPIndex(SqString s,SqString t)  //KMP算法
    {
    
    	int next[MaxSize],i=0,j=0;
    	GetNext(t,next);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{
    			i++;j++;  			//i,j各增1
    		}
    		else j=next[j]; 		//i不变,j后退,现在知道为什么这样让子串回退了吧
        }
        if (j>=t.length)
    		return(i-t.length);  	//返回匹配模式串的首字符下标
        else  
    		return(-1);        		//返回不匹配标志
    }
    

    KMP算法的改进

    为什么KMP算法这么强大了还需要改进呢?
    大家来看一个例子:
    主串s=“aaaaabaaaaac”
    子串t=“aaaaac”
    这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。'c’前的’a’回溯后的字符依然是‘a’。
    我们知道没有必要再将‘b’与‘a’比对了,因为回溯后的字符和原字符是相同的,原字符不匹配,回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为:nextval数组。KMP算法的改进可以简述为: 如果a位字符与它next值指向的b位字符相等,则该a位的nextval就指向b位的nextval值,如果不等,则该a位的nextval值就是它自己a位的next值。 这应该是最浅显的解释了。如字符串"ababaaab"的next数组以及nextval数组分别为:

    下标01234567
    子串ababaaab
    next-10012311
    nextval-10-10-1310

    我们来分析下代码:

    void GetNextval(SqString t,int nextval[])  
    //由模式串t求出nextval值
    {
    	int j=0,k=-1;
    	nextval[0]=-1;
       	while (j<t.length) 
    	{
           	if (k==-1 || t.data[j]==t.data[k]) 
    		{	
    			j++;k++;
    			if (t.data[j]!=t.data[k]) 
    //这里的t.data[k]是t.data[j]处字符不匹配而会回溯到的字符
    //为什么?因为没有这处if判断的话,此处代码是next[j]=k;
    //next[j]不就是t.data[j]不匹配时应该回溯到的字符位置嘛
    				nextval[j]=k;
               	else  
    				nextval[j]=nextval[k];
    //这一个代码含义是不是呼之欲出了?
    //此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
    //用较为粗鄙语言表诉:即字符不匹配时回溯两层后对应的字符下标
           	}
           	else  k=nextval[k];    	
    	}
    
    }
    
    int KMPIndex1(SqString s,SqString t)    
    //修正的KMP算法
    //只是next换成了nextval
    {
    	int nextval[MaxSize],i=0,j=0;
    	GetNextval(t,nextval);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{	
    			i++;j++;	
    		}
    		else j=nextval[j];
    	}
    	if (j>=t.length)  
    		return(i-t.length);
    	else
    		return(-1);
    }
    

    剩下的话

    在写这篇博客时,我想起了编译原理老师讲过的一些知识,其实KMP算法的步骤与自动机有不少相似之处,有兴趣的朋友不妨联系对比一下。

    参考书籍

    《数据结构教程》(第5版) 李春葆
    《大话数据结构》 程杰

    展开全文
  • 数据结构实验括号匹配,本例子是堆栈实现括号匹配
  • 主要介绍了基于PHP实现栈数据结构和括号匹配算法,结合实例形式分析了php数组操作实现栈数据结构的进栈、出栈,以及基于栈的括号匹配应用技巧,需要的朋友可以参考下
  • 利用循环链表实现的括号匹配数据结构实验报告,适合新手,有程序运行截图
  • 利用栈的括号匹配算法 C语言数据结构 利用栈的括号匹配算法 C语言数据结构
  • 数据结构(串匹配—BF算法

    千次阅读 2020-02-17 17:49:57
    BF算法即暴风(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和...
  • 【C++数据结构与算法】括号匹配算法这是从《c++数据结构与程序设计》这本书改过来的一个算法。 会用到c++内置的数据结构栈。要解决的问题:输入一行括号,判断这行括号是否匹配算法原理和代码思路一句话概括算法...
  • * 基于栈实现--括号匹配算法 */ public class BracketMarch { ArrayStack&lt;Character&gt; stack = new ArrayStack&lt;Character&gt;(); public boolean isValid(String s) { for (int i = 0...
  • C语言开发之数据结构算法

    千人学习 2019-03-14 21:23:03
    这是数据结构、算法视频的第三个系列课程。该教程主要讲解二分查找、跳表、base64、散列表、哈希算法、字符串匹配算法等及将他们灵活的运用到算法里面。课程讲解的方式均是先以图形的方式进行分析,然后“手敲”代码...
  • 这本《C++数据结构算法(第4版)》全面系统地介绍了数据结构,并以C++语言实现相关的算法。 主要强调了数据结构算法之间的联系,使用面向对象的方法介绍数据结构,其内容包括算法的复杂度分析、链表、栈、队列、...
  • 数据结构算法 第三章 字符串 张铭 /mzhang/DS/ 北京大学信息科学与技术学院 数据结构算法教学小组 版权所有转载或翻印必究 主要内容 3.1 字符串抽象数据类型 3.2 字符串的存储结构和类定义 3.3 字符串运算的算法...
  • 数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
  • 数据结构 基于字符串模式匹配算法的病毒感染检测问题实验目的实验内容实验提示 实验目的 1.掌握字符串的顺序存储表示方法。 2.掌握字符串模式匹配算法BF算法或KMP算法的实现。 实验内容 问题描述 医学研究者最近发现...
  • 1、串的模式匹配算法 前端时间在复习KMP算法时在网上看到了一篇关于KMP的博文,讲的非常详细,在这里给大家分享下:点击打开链接 在串的模式匹配算法中主要有两种算法,BF算法与KMP算法,在这里我不准备详细介绍这...
  • 数据结构实现顺序串的各种模式匹配算法 注意:本代码为了测试运行默认含有操作所需数据,如有需要可自己增删改相关数据 涉及基本运算流程 建立目标串s=abcabcdabcdeabcdeabcdefabcdefg 和模式串 t =abcdeabcdefab ...
  • 很经典,模式匹配大家都知道,但书上只有一般算法,这里是它的改进算法
  • 数据结构算法实现(严蔚敏版
  • 由于文章有点多,并且发的文章也不是一个系列一个系列发的,不过我的文章大部分都是围绕着 数据结构 + 算法 + 计算机网络 + 操作系统 + Linux + 数据库 这几个方面发的,为了方便大家阅读,我整理了一波。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 240,183
精华内容 96,073
关键字:

数据结构匹配算法

数据结构 订阅