精华内容
下载资源
问答
  • 数据结构 串的模式匹配

    千次阅读 2020-05-05 16:58:00
    全部每周作业和视频思考题答案和解析 见浙江大学 数据结构 思考题+每周练习答案 题目一:若给定文本长度为 n,模式长度为 m,则库函数 strstr 最坏时间复杂度是: A. O(nm) B. O(n) C. O(m) D....

    全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案

    题目一:若给定文本长度为 n,模式长度为 m,则库函数 strstr 的最坏时间复杂度是:

    • A. O(nm)

    • B. O(n)

    • C. O(m)

    • D. O(n+m)

    乍看一眼就是O(nm),当然,我们可以想象到,除非m=1,否则不可能出现正好是n*m次比较的结果。

    题目二:对于 pattern = abcabcacab,最后 3 个字符的 match 值是多少?

    • A. 2, 3, 1

    • B. -1, 0, 1

    • C. -1, 0, -1

    • D. 5, 6, 4

    这个c所在的子串abcac和前面的配不上,而且又和一开始的a配不上,所以为-1,然后a和一开始的a配上了,为0,然后b为1。

    选B

    题目三:如果 match[j] 的值不是满足子序列条件的“最大”i,会出现什么问题?

    如果会出现问题,肯定就是没有匹配到呗。我们思考一下为什么会匹配不到:

    比如 abcabca ,match表示为:

    我觉得这个题目表达是有问题的,但是又不好描述,只能画个图来说说这个思考问题是想干嘛。如果match不取最大i的时候,就可能出现下面这种匹配:蓝色表示能被匹配上的字符子串

    在做匹配的时候,string的abcabca和pattern的abcabcac正好相互匹配,而下一个就不匹配了,所以这个时候a就变为了0。

    感觉这个思考题没什么意义???

    为什么不能直接用 pattern: abcabcacabb 的最后一个能匹配上的子串进行匹配而要用最大的 i 呢?比如这里的最后面的ab

    比如我们要进行匹配的子串是:abcabcacabab.....模式字串为abcabcacabb,如果用abca进行匹配,那么:

     

    展开全文
  • 数据结构 串的模式匹配算法BF、KMP

    千次阅读 2019-01-12 02:27:32
    串的模式匹配 朴素的模式匹配算法(BF(BruteForce)算法) BF的算法实现 算法分析 KMP模式匹配算法 字符串前缀后缀 最长公共前后缀 next数组 kmp算法实现 KMP算法的改进 ​nextval数组实现 串的模式匹配 ...

    目录

    串的模式匹配

    朴素的模式匹配算法(BF(Brute Force)算法)

    BF的算法实现

    算法分析

    KMP模式匹配算法

    字符串前缀后缀

    最长公共前后缀

    next数组

    kmp算法实现

    KMP算法的改进

    ​nextval数组实现


    串的模式匹配

    模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配

    假设P是给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串,这个问题成为模式匹配问题。P称为模式T称为目标。如果T中存在一个或多个模式为P的子串,就给出该子串在T中的位置,称为匹配成功;否则匹配失败。

    朴素的模式匹配算法(BF(Brute Force)算法)

    朴素模式匹配算法的基本思想是穷举法,即就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。

    Brute-Force的基本思想是:从主串S=“S(0) S1 ...S(n-1)”的第pos个字符开始与子串T=“T(0) T1 ...T(n-1)”的第一个字符比较,如果相等则继续比较后一个字符否则从主串的下一字符开始与子串T的第一个字符重新开始比较,以此类推。如果在主串S中存在与子串T相等的连续字符序列,则匹配成功,函数返回子串T中第一个字符在主串S中的位置;否则,函数返回-1。简单的说,就是对主串的每一个字符作为子串的开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做T的长度的小循环,直到匹配成功或全部遍历完成为止。

    假设我们要从主串S=“goodgoogle”中,找到T=“google”这个子串的位置。步骤如下:

    1、主串S的第一位开始,S与T的前三个字母都匹配成功,但S的第四个字母是d 而 T的是g。第一位匹配失败。如图所示,竖直连线表示相等,弯折线表示不等,如图所示:

    2、主串S第二位开始,主串S首字母为o,模式串T的首字母为g,匹配失败,如图所示:

    3、主串S第三位开始,主串S首字母为o,模式串T的首字母为g,匹配失败,如图所示:

    4、主串S第四位开始,主串S首字母为d,模式串T的首字母为g,匹配失败,如图所示:

    5、主串S第五位开始,S与T,6个字母全匹配,匹配成功,如图所示:

    BF的算法实现

    /*  
    函数 int BF(const char *s,const char *sub,int pos) 从目标s的首位位置开始模式匹配,  
    用模式sub匹配s,寻找首个sub子串并返回其下标位置。若整个匹配过程失败,返回-1。
    */
    
    int BF(const char *s,const char *sub,int pos)
    {
        int slen = strlen(s);     //目标的长度  
        int sublen = strlen(sub); //模式的长度   
    
        int i = pos;  //目标的下标变量   
        int j = 0;    //模式的下标变量  
        
        while(i < slen && j < sublen)
        {
            if(s[i] == sub[i])
            {
                i++;     //继续比较后续字符 
                j++;
            }
            else    //指针退回重新开始匹配
            {
                i = i - j + 1;   //i退回上次匹配首位的下一位
                j = 0;      //j退回子串的首位
            }
        }
        if(j >= sublen)
        {
            return i - j;
        }
        return -1;
    }

    算法分析

    若模式子串的长度是m,目标穿的长度是n,这时最坏的情况是每遍比较都在最后出现不等,即每遍最多比较m次,最多比较n-m+1遍,总的比较次数最多为m(n-m+1),因此朴素的模式匹配算法的时间复杂度为O(mn)。朴素的模式匹配算法中存在回溯,这影响到匹配算法的效率,因而朴素的模式匹配算法在实际应用中很少采用。在实际应用主要采用无回溯的匹配算法,KMP算法和BM算法均为无回溯的匹配算法。

    KMP模式匹配算法

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

    在学习KMP算法之前,我们先需要准备大量的前置知识。

    字符串前缀后缀

    何为前缀后缀?简单来说,将一个字符串在任意位置分开,得到的左边部分即为前缀,右边部分即为后缀。例如对于字符串"abcd",它的前缀有"a","ab","abc";后缀有"d","cd","bcd"。注意前后缀均不包括字符串本身

    最长公共前后缀

    对于一个字符串来说,它既有前缀,又有后缀,所谓的最长公共前后缀,即该字符串最长的相等的前缀和后缀。例如上面的字符串"abcd"就没有公共前后缀,更别提最长了,因为它的前后缀里就没有相等的;而字符串"abcab"就有一个最长的公共前后缀即"ab"。

    那么求最长公共前后缀到底有什么用呢?我们先来分析BF解法中的操作,若不匹配,主串的下一字符开始与子串T的第一个字符重新开始比较

    在kmp算法中,若是上述情况,为最后一个元素 D 失配,则D之前的元素都被成功匹配,D之前为AB,模式的首部两位也是AB,则接下来比较的是第三位 C (注意此时主串中的匹配字符位置不变,即无回溯,主串在匹配过程中一直在向前遍历)如下图

    我们看到 原串 中字符 与 D 失配后,直接将 C 与 原串中该字符进行比较,原因是 D 之前的 串的最长公共前后缀长度为 2,即 若D失配后,我们根据此最长公共前缀的值来确定下个需要匹配的字符,即为模式中的第三个字符,2号下标,这就是kmp的核心,避免了不必要的匹配,提高了匹配的效率。

    next数组

    next数组是kmp算法的核心,它表明了若模式中的某字符在主串中匹配失败后,下次需要匹配的模式中的字符。

    网上的博客中有很多next数组的版本,如严蔚敏《数据结构》中模式串从1号下标,开始为了清晰期间,本文在这里做如下规则约束:

    • 模式串从0号下标开始
    • next[0] = -1
    • next[1] = 0

    关于next数组的定义有数学方式,难于理解,接下来先讲解next数组的使用方法与求解方式,最后我们给出数学公式定义。

    例:对于模式 abcababcabc,它的next数组如下

    接下来我们分析 next[j] 的含义

    • next[0] = -1
    • next[1] = 0
    • next[2] = 0,表示若 c 匹配失败,下次匹配时从模式中下标为0的字符,即a,从头开始。
    • next[3]同上
    • next[4]  = 1,表示若4号下标 b 匹配失败,下次匹配时从模式中下标为1的字符,即b开始,因为4号下标失配,则之前的a已被匹配,恰好模式0号下标正好为a,则下次从0号下标后即1号下标进行匹配
    • next[5] = 2,表示若5号下标 a 匹配失败,下次匹配时从模式中下标为2的字符,即c开始,因为5号下标失配,则之前的ab已被匹配,恰好模式0、1号下标正好为ab,则下次从1号下标后即2号下标进行匹配
    • next[6] = 1,表示若6号下标 b 匹配失败,分析同next[4]
    • next[7] = 2,表示若7号下标 c 匹配失败,分析同next[5]
    • next[8] = 3,表示若8号下标 a 匹配失败,下次匹配时从模式中下标为3的字符,即a开始,因为8号下标失配,则之前的abc已被匹配,恰好模式0、1、2号下标正好为abc,则下次从2号下标后即3号下标进行匹配
    • next[9] = 4,表示若9号下标 b 匹配失败,下次匹配时从模式中下标为4的字符,即b开始,因为9号下标失配,则之前的abca已被匹配,恰好模式0、1、2、3号下标正好为abca,则下次从3号下标后即4号下标进行匹配
    • next[10] = 5,表示若10号下标 c 匹配失败,下次匹配时从模式中下标为5的字符,即a开始,因为10号下标失配,则之前的abcab已被匹配,恰好模式0、1、2、3、4号下标正好为abcab,则下次从4号下标后即5号下标进行匹配

    结论:next[i] 的值为 i 号下标之前的串 的 最长公共前后缀的值

    next数组的几个练习

    例1:

    例2:

    例3:

    例4:

    例5:

    例6:

    例7:

    next数组实现

    void GetNext(int *next,const char *sub)
    {
    	int lensub = strlen(sub);
    
    	next[0] = -1;
    	next[1] = 0;
    	int i = 2;
    	int k = 0;
    	while(i < lensub)
    	{
    		if((k == -1) || sub[k] == sub[i-1])
    		{
    			next[i++] = ++k;
    		}
    		else
    		{
    			k = next[k];
    		}
    	}
    }

    kmp算法实现

    KMP算法中每一次的匹配:

    • 主串的起始位置 = 上一轮匹配的失配位置;
    • 模式串的起始位置 = 失配位置的next值
    int KMP(const char *s,const char *sub,int pos)
    {
    	int lens = strlen(s);//n
    	int lensub =  strlen(sub);//m
    
    	int i = pos;//主串的pos
    	int j = 0;//子串
    	
    	int *next = (int *)malloc(sizeof(int) * lensub);
    	GetNext(next,sub);
    
    	while(i < lens && j < lensub)
    	{
    		if((j == -1) || s[i] == sub[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = next[j];//与 BF算法的不同之处,失配后下次模式中开始匹配的位置为失配位置的next值
    		}
    	}
    
    	if(j >= lensub)
    	{
    		return i-j;
    	}
    	return -1;
    }

    KMP算法的改进

    对kmp算法的改进其实就是对next数组的改进因为next数组在某些情况下仍然是有缺陷的,不够高效

    例如在模式串 s =  ’aaaab’  和 主串 t = ’aaabaaaab’ 匹配时,当在 i=3(b) , j=3(a) 时,产生失配,由下图的next数组中指出还需进行 i=3,j=2;i=3,j=1;i=3,j=0这三次比较。但是我们发现这样的比较是没有意义的,因为s串中前四个字符都相等所以不需要逐个与主串中的第4个字符进行比较。

    所以此时我们应该考虑直接进行 i=4,j=0 的比较,这就是说,在我们求出next[j] = k时,而模式串中s[j] = s[k],则当匹配字符s[j]和t[i] 比较不等时,不需要再进行 s[k] 和 t[i]的比较,而是直接和 s[next[k]] 比较,换句话说就是如果存在 s[j] = s[k],那么next[j] = next[k]。

    求nextval数组值有两种方法,一种是不依赖next数组值直接用观察法求得,一种方法是根据next数组值进行推理

    nextval求解练习:



    nextval数组实现

    void GetNextVal(int *nextval,const char *sub)
    {
    	int lensub = strlen(sub);
    	int *next = (int *)malloc(sizeof(int) * lensub);
    	GetNext(next,sub);
    
    	for (int i = 0; i < lensub; i++)  // 将next数组全部写入nextval
    	{
    		nextval[i] = next[i];
    	}
    
    	int i = 1;
    
    	// 接下来我们将next数组中所有sub[next[i]] 与 sub[i]相等的i的nextval改为nextval[next[i]]
    	while (i < lensub)
    	{
    		if (sub[i] == sub[next[i]]) // 当sub[next[i]] 与 sub[i] 相等时,我们做以优化
    		{
    			nextval[i] = nextval[next[i]];  // 把nextval[next[i]] 的值 赋给 nextval[i]
    		}
    		i++;
    	}
    }

     

    展开全文
  • 转载自http://www.cnblogs.com/dolphin0520/ 十分感谢作者大大 KMP算法 KMP算法 在介绍KMP算法之前,先介绍一下BF算法。 一.BF算法 ... BF算法是普通的模式匹配算法,BF算法的思想就是将...

    转载自http://www.cnblogs.com/dolphin0520/

    十分感谢作者大大

    KMP算法

     

                                                                 KMP算法

            在介绍KMP算法之前,先介绍一下BF算法。

    一.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    第四趟:ababcababa    第五趟:ababcababa

                 ababa                            ababa                          ababa                        ababa                       ababa

                j=0                                   j=1                            j=2                         j=3                         j=4(i和j回溯)

     

                  i=1                                 i=2                           i=3                            i=4                        i=3

     第六趟:ababcababa         第七趟:ababcababa       第八趟:ababcababa     第九趟:ababcababa   第十趟:ababcababa

                  ababa                              ababa                           ababa                        ababa                        ababa

                 j=0                                  j=0                           j=1                           j=2(i和j回溯)            j=0

     

                  i=4                                    i=5                          i=6                           i=7                          i=8

    第十一趟:ababcababa       第十二趟:ababcababa    第十三趟:ababcababa   第十四趟:ababcababa   第十五趟:ababcababa

                         ababa                               ababa                           ababa                          ababa                          ababa

                   j=0                                    j=0                         j=1                            j=2                         j=3

     

                        i=9

    第十六趟:ababcababa

                           ababa

                        j=4(匹配成功)

    代码实现:

    复制代码
    int BFMatch(char *s,char *p)
    {
        int i,j;
        i=0;
        while(i<strlen(s))
        {
            j=0;
            while(s[i]==p[j]&&j<strlen(p))
            {
                i++;
                j++;
            }
            if(j==strlen(p))
                return i-strlen(p);
            i=i-j+1;                //指针i回溯
        }
        return -1;    
    }
    复制代码
       其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=p0p1p2p3,又因为p0!=p1!,所以第六趟的匹配是多余的。又由于p0==p2,p1==p3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。

    二.KMP算法

        KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。

      在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

      对于next[]数组的定义如下:

     1) next[j] = -1  j = 0

     2) next[j] = max(k): 0<k<j   P[0...k-1]=P[j-k,j-1]

     3) next[j] = 0  其他

     如:

     P      a    b   a    b   a

     j      0    1   2    3   4

     next    -1   0   0    1   2

     即next[j]=k>0时,表示P[0...k-1]=P[j-k,j-1]

     因此KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。

    代码实现如下:

    复制代码
    int KMPMatch(char *s,char *p)
    {
        int next[100];
        int i,j;
        i=0;
        j=0;
        getNext(p,next);
        while(i<strlen(s))
        {
            if(j==-1||s[i]==p[j])
            {
                i++;
                j++;
            }
            else
            {
                j=next[j];       //消除了指针i的回溯
            }
            if(j==strlen(p))
                return i-strlen(p);
        }
        return -1;
    }
    复制代码

      因此KMP算法的关键在于求算next[]数组的值,即求算模式串每个位置处的最长后缀与前缀相同的长度, 而求算next[]数组的值有两种思路,第一种思路是用递推的思想去求算,还有一种就是直接去求解。 

    1.按照递推的思想:

       根据定义next[0]=-1,假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]

       1)若P[j]==P[k],则有P[0..k]==P[j-k,j],很显然,next[j+1]=next[j]+1=k+1;

       2)若P[j]!=P[k],则可以把其看做模式匹配的问题,即匹配失败的时候,k值如何移动,显然k=next[k]。

       因此可以这样去实现:

    复制代码
    void getNext(char *p,int *next)
    {
        int j,k;
        next[0]=-1;
        j=0;
        k=-1;
        while(j<strlen(p)-1)
        {
            if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]
            {
                j++;
                k++;
                next[j]=k;
            }
            else                   //p[j]!=p[k]
                k=next[k];
        }
    }
    复制代码
     
       2.直接求解方法
    复制代码
    void getNext(char *p,int *next)
    {
        int i,j,temp;
        for(i=0;i<strlen(p);i++)
        {
            if(i==0)
            {
                next[i]=-1;     //next[0]=-1
            }
            else if(i==1) 
            {
                next[i]=0;      //next[1]=0
            }
            else
            {
                temp=i-1;
                for(j=temp;j>0;j--)
                {
                    if(equals(p,i,j))
                    {
                        next[i]=j;   //找到最大的k值
                        break;
                    }
                }
                if(j==0)
                    next[i]=0;
            }
        }
    }
    
    bool equals(char *p,int i,int j)     //判断p[0...j-1]与p[i-j...i-1]是否相等  
    {
        int k=0;
        int s=i-j;
        for(;k<=j-1&&s<=i-1;k++,s++)
        {
            if(p[k]!=p[s])
                return false;
        }
        return true;
    }
    复制代码

    转载于:https://www.cnblogs.com/lnlin/p/6885812.html

    展开全文
  • 串的模式匹配 设有主串s和子串t, 子串t的定位就是要在s中找到一个与子串相等的子串。 通常把主串s称为目标串, 把子串t称为模式串, 因此定位也称作模式匹配。 在目标串s中找到一个模式串t, 称为模式匹配成功。 在...

    串的模式匹配

    设有主串s和子串t, 子串t的定位就是要在s中找到一个与子串相等的子串。
    通常把主串s称为目标串, 把子串t称为模式串, 因此定位也称作模式匹配。
    在目标串s中找到一个模式串t, 称为模式匹配成功。
    在目标串s中找到一个模式串t, 称为模式匹配不成功。

    Brute-Force算法

    Brute-Force算法简称为BF算法, 亦称为简单匹配算法。
    这个算法又称为暴力匹配。
    假设我们用i和j分别代表主串与模式串当前比较的位置,如果当前匹配成功, 则i++,j++;若失败, 则两个指针都要回溯。
    i = i - j + 2, j则是从头开始。

    BF算法在最好的情况下是O(m)O(m)的复杂度, 即主串的前m个字符正好等于模式串的m个字符。
    在最坏的情况下时间复杂度为O(nm)O(n * m)

    KMP算法

    KMP算法是由
    D. E. Knuth、J.H.Morris和V.R.Pratt共同提出的算法, 简称KMP算法。
    该算法较BF算法有较大的改进, 主要是消除了主串指针的回溯, 从而使算法效率有了某种程度的提高。

    在KMP算法中, 通过分析模式串t从中提取出隐藏的加速匹配的有用信息, 利用它来提高模式匹配的效率。

    采用next数组存放这些“部份匹配”信息。
    t = “ababb” t4前面:t0t1 = t2t3;
    在这里插入图片描述
    记住, 一定要是t的开头部份。
    比如abaaabc 此时字符c前面有两个与t开头部份相同的字符。那么next[i] = 2;i是c的下标。假设有多个这样相同的情况,则我们取最大的。

    Next例:

    在这里插入图片描述

    在KMP算法中求next数组的时间复杂度为O(m)O(m),在后面的匹配中因主串s的下标不减即不回溯, 比较次数可记为n,所以KMP算法的总时间复杂度为O(n+m)O(n + m)
    在这里插入图片描述

    展开全文
  • 数据结构与算法实验指导 V2017 常熟理工学院 数据结构与算法实验指导与报告书 _2017-2018_学年 第_1_ ...1 数据结构与算法实验指导 V2017 实验四 串与模式匹配 实验目的 1掌握串的存储表示及基本操作 2掌握串的两种模式
  • 主要介绍了C语言数据结构串的模式匹配的相关资料,需要的朋友可以参考下
  • 键盘输入目标串(主串)s、模式串(子串)t,编写程序,实现顺序串的BF模式匹配算法。要求:匹配成功,输出位序,匹配不成功,显示相应提示信息。 例如:s=“aaaabcdcccc”,t=“abcd”。 因为程序很简单,所以就...
  • 要点:子串的第一个字符匹配成功主串的字符后就依次匹配子串后面的字符,直到子串匹配结束 代码: public static int forceMatch(char[] mainString,char[] pattern){ int i = 0; int j = 0; //回溯的指针 int...
  • 子串在主串中的定位操作称为串的模式匹配,记为index(s,t,pos),即在主串s中,从第pos个字符开始查找与子串t第一次相等的位置。若查找成功,则返回子串t的第一个字符在主串中的位序,否则返回0。其中主串称为目标串...
  • 数据结构——串的模式匹配算法

    千次阅读 2017-05-10 18:11:09
    2、串的模式匹配算法  串的查找操作也称作串的模式匹配操作,模式匹配操作的具体含义是:在主串(也称作目标串)中,从位置start开始查找是否存在子串(也称作模式串),如在主串中查找到一个与模式串相同的子串,...
  • 串:串的模式匹配模式匹配的定义:实现代码: 模式匹配的定义: 实现代码: int Index(SString S,SString T,int pos){ int i = pos,j = 1; while(i <= S.length && j <= T.length){ if(S.ch[i] =...
  • 参考资料:《数据结构(C语言版)严蔚敏著》 版权说明:未经作者允许,禁止转载。...模式匹配:在S中定位某个子串T操作称为模式匹配,其中S称为目标T称为模式。 匹配成功:在模式...
  • 数据结构- 串的模式匹配算法 BF和 KMP算法
  • 数据结构 串模式匹配 KMP算法

    千次阅读 2019-03-13 21:23:26
    KMP算法应用于串的模式匹配中 普通模式匹配算法在进行匹配时需要频繁对主串指针进行回溯,KMP算法通过将模式向右滑动一段距离的方式避免了主串的回溯,同时降低了算法复杂度 ,由原来的O(n*m)变为O(n)。 KMP...
  • 思路:将目标S第一个字符与模式串T第一个字符进行匹配,若相等,则继续比较S第二个字符和 T第二个字符;若不相等,则比较S第二个字符和T第一个字符,依次比较下去,直到得出最后的匹配结果。 代码...
  • 数据结构_串_串的模式匹配_KMP/BF
  • 这里说了些什么? 在这个章节讲了串的结构、构造串的方法、各种对串的操作以及从串的匹配的算法。 串的结构也是千奇百态,有直接按...模式匹配算法是传统的BF算法(一个一个比失败了就挪动一个位置继续比)和KM...
  • 串的模式匹配写在前面1.头文件及类型定义2.串类型定义3.函数声明4.基本操作4.1 初始化串4.2 赋值操作4.3 朴素(简单)模式匹配算法1★★4.4 朴素(简单)模式匹配算法2★★4.5 求next数组★★★4.6 KMP算法★★★4.7 ...
  • /* 串的模式匹配 */ /* BF简单匹配算法 */ int BF_match(SqString s,SqString t){ int i=0,j=0; while(i<s.length&&j<t.length){ if(s.data[i]==t.data[j]){//继续匹配下一个字符 i++; ...
  • BF全称为Brute-Force,最简单直观的模式匹配算法。 1.算法思想 两个字符串进行匹配时,一个主串和一个模式串,就是按照我们最容易想到的算法来进行匹配。用两个变量i,j分别记录主串和模式串的匹配位置,如果两者在...
  • *串的模式匹配-BF算法 *找到相同的字符串输出在原字符串中的位置 代表匹配字符串在原字符串中的位置 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define STRSIZE 255//字符串的...
  • 这里先给出之前我参考博客网址,以及参考书籍是数据结构(严蔚敏)。参考代码网址这里我总结一下我思路。先介绍一些基本概念 主:这里指是要匹配的字符 模式串:需要在主中寻找字符 KMP匹配算法...
  • 该文档描述了数据结构串的相关知识,朴素的模式匹配,KMP模式匹配,相关的概念,基本知识和代码的实现
  • 目录 概念 简述 KMP算法原理 代码 计算next数组 ...从s中匹配t,在BF算法中,通过指针回溯不断进行匹配,其思想是穷举。...当然,计算机不会像人这么敏感,但是能否设计出一种算法,提高类似这种模式匹配的...
  • #include #include #include typedef struct { char *ch; int length;...printf("请输入第一个:\n");...printf("请输入第二个:... printf("请输出子串在主位置:\n"); printf("%d\n",k); return 0; }

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,808
精华内容 723
关键字:

数据结构串的模式匹配

数据结构 订阅