精华内容
下载资源
问答
  • KMP模式匹配算法中next和nextval的求解

    千次阅读 2015-12-08 16:42:12
    KMP算法是模式匹配专用算法。 它是在已知模式串的next或nextval数组的基础上执行的。...第二部分,利用计算好的模式串的nextval数组,进行模式匹配。    KMP算法中有next数组和nextval数组之分。他们代表的意义

    KMP算法是模式匹配专用算法。

    它是在已知模式串的next或nextval数组的基础上执行的。如果不知道它们二者之一,就没法使用KMP算法,因此我们需要计算它们。

    KMP算法由两部分组成:

    第一部分,计算模式串的next或nextval数组。

    第二部分,利用计算好的模式串的nextval数组,进行模式匹配。

     
        KMP算法中有next数组和nextval数组之分。他们代表的意义和作用完全一样,完全可以混用。  唯一不同的是,next数组在一些情况下有些缺陷,而nextval是为了弥补这个缺陷而产生的。

    一、求解next

    步骤:next数组值的程序设计求解方法:首先可以肯定的是第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。

    举例:
    模式串  c
    next值  2
    1.前两位必为0,1。
    2.计算第三位的时候,看第二位b的next值,为1,则把b和1对应的a进行比较,不同,则第三位a的next的值为1,因为一直比到最前一位,都没有发生比较相同的现象。
    3.计算第四位的时候,看第三位a的next值,为1,则把a和1对应的a进行比较,相同,则第四位a的next的值为第三位a的next值加上1,为2。因为是在第三位实现了其next值对应   
    的值与第三位的值相同。
    4.计算第五位的时候,看第四位a的next值,为2,则把a和2对应的b进行比较,不同,则再将b对应的next值1对应的a与第四位的a进行比较,相同,则第五位的next值为第二位b的   
    next值加上1,为2。因为是在第二位实现了其next值对应的值与第四位的值相同。
    5.计算第六位的时候,看第五位b的next值,为2,则把b和2对应的b进行比较,相同,则第六位c的next值为第五位b的next值加上1,为3,因为是在第五位实现了其next值对应的   
    值与第五位相
    6.计算第七位的时候,看第六位c的next值,为3,则把c和3对应的a进行比较,不同,则再把第3位a的next值1对应的a与第六位c比较,仍然不同,则第七位的next值为1。
    7.计算第八位的时候,看第七位a的next值,为1,则把a和1对应的a进行比较,相同,则第八位c的next值为第七位a的next值加上1,为2,因为是在第七位和实现了其next值对应的值与第七位相同。

    二、求解nextval:

           求nextval数组值有两种方法,一种是不依赖next数组值直接用观察法求得,一种方法是根据next数组值进行推理,两种方法均可使用,视更喜欢哪种方法而定。
    
        本文主要分析nextval数组值的第二种方法:
    
      模式串      a b a a b c a c
    
      next值      0 1 1 2 2 3 1 2
    
      nextval值 0 1 0 2 1 3 0 2
    
    
    
      1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。
    
      2.第三位的next值为1,那么将第三位和第一位进行比较,均为a,相同,则,第三位的nextval值为0。
    
      3.第四位的next值为2,那么将第四位和第二位进行比较,不同,则第四位的nextval值为其next值,为2。
    
      4.第五位的next值为2,那么将第五位和第二位进行比较,相同,第二位的next值为1,则继续将第二位与第一位进行比较,不同,则第五位的nextval值为第二位的next值,为1。
    
      5.第六位的next值为3,那么将第六位和第三位进行比较,不同,则第六位的nextval值为其next值,为3。
    
      6.第七位的next值为1,那么将第七位和第一位进行比较,相同,则第七位的nextval值为0。
    
      7.第八位的next值为2,那么将第八位和第二位进行比较,不同,则第八位的nextval值为其next值,为2。
    
    
    
    三、next和nextval比较
    
    

    Next数组的缺陷举例如下:

    比如主串是“aab…..” 省略号代表后面还有字符。

     模式串“aac”

    通过计算aac的next数组为012(另外,任何字符串的第二位字符的next总是1,因此你可以认为他固定为1)

    当模式串在字符c上失配时,会跳到第2个字符,然后再和主串当前失配的字符重新比较,即此处用模式串的第二个a和主串的b比较

    即aab                  aac

    显然a也不等于b。然后会跳到1,接着比,然后又失配,直到最后才使主串后移一位。

    而“aac”的nextval数组为002当在c失配时会跳到2,若还失配就直接跳到0,比next数组少比较了1次。

    在如果模式串很长的话,那可以省去很多比较,因此你应该使用nextval数组。


    四、严蔚敏

    上:http://v.youku.com/v_show/id_XODYxNjExODQ=.html    第 34分钟开始 

       下:http://www.56.com/u28/v_NjAwMzA0ODA.html     

    五、代码实现:
    
        public static void main(String [] args) throws IOException{//main函数,输入主串和模式串
    
            System.out.print("请输入主串:");
    
            Scanner sn1 = new Scanner(System.in);
    
            String s1 = sn1.next();
    
            System.out.print("请输入模式串:");
    
            Scanner sn2 = new Scanner(System.in);
    
            String s2 = sn2.next();
    
            char [] s3 = s1.toCharArray();
    
            char [] s4 = s2.toCharArray();
    
            System.out.print(KMP_test(s3,s4));
    
        }
    
        
    
        public static int KMP_test(char [] s, char [] t){// 主串顺序匹配
    
            int [] next = next(t);
    
            int i = 0, j = 0;
    
            while(i
    
                if(j == -1 || s[i] == t[j]){
    
                    ++i;
    
                    ++j;
    
                }else{
    
                    j = next[j];
    
                }
    
            }
    
            System.out.println(i);
    
            if(j
    
                return 0;
    
            }else{
    
                return i-t.length;
    
            }
    
        }
    
        
    
        public static int [] next(char [] t){// next函数求解
    
            int i = 0, j = -1;
    
            int [] next = new int[t.length];
    
            next[0] = -1;
    
            while(i
    
                if(j == -1 || t[i] == t[j]){
    
                    ++i;
    
                    ++j;
    
                    next[i] = j;
    
                }
    
                else
    
                    j = next[j];
    
            }
    
            System.out.println(Arrays.toString(next));
    
            return next;
    
        }
    
    对于改进的KMP算法,只需要把next函数换为nextval函数就行了
    
        public static int [] next(char [] t){
    
            int i = 0, j = -1;
    
            int [] next = new int[t.length];
    
            next[0] = -1;
    
            while(i
    
                if(j == -1 || t[i] == t[j]){
    
                    ++i;
    
                    ++j;
    
                    if (t[i] != t[j]) {  
    
                        next[i] = j;  
    
                    } else {  
    
                        next[i] = next[j];  
    
                    } 
    
                }
    
                else
    
                    j = next[j];
    
            }
    
            System.out.println(Arrays.toString(next));
    
            return next;
    
        }
    展开全文
  • 题目:设字符串S=‘aabaabaabaac...(2)若S作主串,P作模式串,试分别写出利用BF算法和KMP算法的匹配过程。 (可以参考 课本80页 图4.3、图4.4的匹配过程描述形式。在每一趟匹配后面 备注该趟结束时i和j的值。) ...

    题目:设字符串S=‘aabaabaabaac’,P=‘aabaac’

    (1)给出S和P的next值和nextval值;

    (2)若S作主串,P作模式串,试分别写出利用BF算法和KMP算法的匹配过程。

    (可以参考 课本80页 图4.3、图4.4的匹配过程描述形式。在每一趟匹配后面 备注该趟结束时i和j的值。)
    在这里插入图片描述

    展开全文
  • 朴素匹配 朴素匹配又称暴力匹配,其时间复杂度为O(m*n) 缺点:时间复杂度高 例如:在ABEECDEEF中查找是否有子串EEF 1. ABEECDEEF EEF 将A于E匹配发现不相同,子串回到起点,主串后移一位 2. ABEECDEEF ...

    朴素匹配

    朴素匹配又称暴力匹配,其时间复杂度为O(m*n)

    缺点:时间复杂度高

     

    例如:在ABEECDEEF中查找是否有子串EEF

    1.

    ABEECDEEF

    EEF

    将A于E匹配发现不相同,子串回到起点,主串后移一位

    2.

    ABEECDEEF

    EEF

    B与E匹配发现不相同,子串回到起点,主串后移一位

    3.

    ABEECDEEF

    EEF

    E与E匹配成功,子串和主串都后移一位,继续匹配

    4.

    ABEECDEEF

    EEF

    此时,E与E匹配相同,子串和主串都后移一位,继续匹配

    5.

    ABEECDEEF

    EEF

    此时F与C匹配不相同 ,子串回到起点,主串回到第一个匹配上的字符的下一个位置(回到第二个E)

    6.

    ABEECDEEF

    EEF

    继续匹配,直至遇到第一个匹配上的字符

    ......

    7.

    ABEECDEEF

    EEF

    E与E匹配相同,子串和主串都后移一位,继续匹配

    8.

    ABEECDEEF

    EEF

    E与E匹配相同,子串和主串都后移一位,继续匹配

    9.

    ABEECDEEF

    EEF

    F与F匹配相同此时子串已匹配完,匹配完成

     

    代码如下:

    #include<stdio.h>
    #include<assert.h>
    #include<string.h>
    int BF(const char *str,const char *sub,int pos)
    {
    	assert(str != NULL && sub != NULL);
    	int i = pos;
    	int j = 0;
    	int lens = strlen(str);
    	int lensub = strlen(sub);
    
    	while(j < lensub && i < lens)
    	{
    		if(str[i] == sub[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i = i-j+1;
    			j = 0;
    		}
    	}
    	if(j >= lensub)
    	{
    		return i-j;
    	}
    	else
    	{
    		return -1;
    	}
    }
    

    KMP算法    

    KMP算法是对朴素匹配的一个优化,在于匹配不成功时,子串有时可以不用回到起点,主串不用回到之前的某个位置

    其时间复杂度为O(m+n),过程如下:

    1.

            BBC ABCDAB ABCDABCDABDE

            ABCDABD

    B与A不匹配,所以主串后移一位。

    2.

            BBC ABCDAB ABCDABCDABDE

            ABCDABD

    因为B与A不匹配,主串再往后移。

    3.

            BBC ABCDAB ABCDABCDABDE

            ABCDABD

           就这样,直到主串有一个字符,与子串的第一个字符相同为止。

    4.

            BBC ABCDAB ABCDABCDABDE

            ABCDABD

    接着比较子串和主串的下一个字符,还是相同。

    5.

            BBC ABCDAB ABCDABCDABDE

            ABCDABD

    直到主串有一个字符,与子串对应的字符不相同。(此时,空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。)

    空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

                      移动位数 = 已匹配的字符数 - 对应的部分匹配值

    所以,将子串回退4位,继续匹配

    6.

            BBC ABCDAB ABCDABCDABDE

            ABCDABD

           空格与C不匹配,这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。

           所以,移动位数 = 2 - 0,结果为 2,于是将子串回退2位

          7.

            BBC ABCDAB ABCDABCDABD

            ABCDABD

           空格与A不匹配,主串后移一位

           8.

      BBC ABCDAB ABCDABCDABDE

             ABCDABD
           逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,将子串回退4位。

          9.

           BBC ABCDAB ABCDABCDABDE

           ABCDABD

         逐位匹配

         10.

          BBC ABCDAB ABCDABCDABDE

          ABCDABD

    直到搜索词的最后一位,发现完全匹配,于是匹配完成

     

    代码如下:

    int Kmp(const char *str,const char *sub,int pos)
    {
    	int i = pos;
    	int j = 0;
    	int lens = strlen(str);
    	int lensub = strlen(sub);
    	int *next = (int *)malloc(sizeof(int) * lensub);
    	assert(next != NULL);
    	GetNext(next,sub);
    	while(j < lensub && i < lens)
    	{
    		if(j == -1 || str[i] == sub[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    	if(j >= lensub)
    	{
    		return i-j;
    	}
    	else
    	{
    		return -1;
    	}
    }

    next数组(部分匹配值)

           next数组就是一个模式串的前缀和后缀的最大公共串长度

     

           "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;

     

          "后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

     

          拿上述KMP算法的例子来说,求子串“ABCDABD”的next数组过程如下:

    1.

          A B C D A B D

         -1 0

    默认next[0]=-1,next[1]=0

    2.

        A B C D A B D

        -1 0 0

    "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

    3.

        A B C D A B D
       -1 0 0 0

    "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

    4.

        A B C D A B D

       -1 0 0 0 0

    "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

    5.

        A B C D A B D

       -1 0 0 0 0 1

     "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

    6.

         A B C D A B D

        -1 0 0 0 0 1 2

    "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

    代码如下:

    void GetNext(int *next,const char *sub)
    {
    	next[0] = -1;
    	next[1] = 0;
    	int lensub = strlen(sub);
    	int i = 2;//当前的i
    	int k = 0;//前一项的K值
    	while(i < lensub)
    	{
    		if(k == -1 || sub[i-1] == sub[k])
    		{
    			next[i] = k+1;
    			i++;
    			k = k+1;
    		}
    		else
    		{
    			k  = next[k];
    		}
    	}
    }

     

    nextval

    下标0123456
    模式串(P)ABCDABD
    next-1000012
    nextval-1000-102

    nextval数组的值怎么来的呢??????????

    默认nextval[0]=-1

    从1号下标开始比较,B和next[0]下标对应的A是否相等    (竖着看 竖着看!!同一列 )

    相等时  nextval[1]=A的nextval值

    相等时 nextval[1]=B的next值

    从2号下标开始比较,C和next[0]下标对应的A是否相等  

    相等时  nextval[1]=A的nextval值

    相等时 nextval[1]=Cnext值

    以此类推.....

     

    代码如下:

    void GetNextval(int *next,const char *sub)
    {
    	nextval[0] = -1;
    	int lensub = strlen(sub);
    	int i = 1;//当前的i
    	int k = -1;//前一项的K值
    	while(i < lensub)
    	{
    		if(k == -1 || sub[i-1] == sub[k])
    		{
    			i++;
    			k = k+1;
    			if (nextval[i] != p[j])
    			{
    				nextval[i] = k;
    			}	
    			else
    			{
    				nextval[i] = nextval[k];
    			}
    		}
    		else
    		{
    			k  = nextval[k];
    		}
    	}
    }

     

     

     

     

     

     

    KMP算法 C语言  next数组

    展开全文
  • KMP模式匹配算法优化(由next[]→nextval[]) 优化方向:在匹配时减少回溯次数,以主串部分ababac和子串ababax匹配为例,显然两段末尾不同,但是计算机需要将前面都匹配一遍,直到最后,回溯时可能一次也回不到相应...

    KMP模式匹配算法优化(由next[]→nextval[])

    优化方向:在匹配时减少回溯次数,以主串部分ababac和子串ababax匹配为例,显然两段末尾不同,但是计算机需要将前面都匹配一遍,直到最后,回溯时可能一次也回不到相应位置,造成循环次数增加,所以在next[]数组的基础上推导出更为合理的回溯方案nextval[]数组回溯

    所以说,如果你之前用next[]数组做出来了,只需要得到在next[]数组基础上得到nextval[]数组,在接下来的匹配查找时,直接将循环体内部的next[]改为nextval[]即可,不过你需要注意的是,弄清楚你原来的next[]数组是从0开始还是从1开始的,这影响到next[]→nextval[]的转化和匹配查找的进行

    一、next[]数组到nextval[]数组的推导

    下面讲一讲两种nextval[]的推导,一种是next[]数组从1开始存放数值的,另一种是next[]数组从0开始存放数值的,以子串str[] = "ababax"为例:

    1)第一种next[]数组是程杰《大话数据结构》中的典例,他用到的next[]数组是从1开始,这样做的好处,就是说让字符的序号与数组序号对应,对于接下来的处理,无论是将next[]处理为nextval[],还是用next[]或者nextval[]进行匹配查找都非常方便

    思路 && 做法:由next[]数组推导nextval[]数组,需要用到原始字符串ababax,因为next[]是str[]推导来的,所以str[]也是从1开始的,str[1] = a, str[2] = b…str[6] = x,做法就显而易见了,令nextval[1] = 0,从第二位开始,如果第j位对应的字符与第next[j]位对应的字符相等,那么nextval[j] = nextval[next[j]],如果不相等就将next[]数组值填入nextval[],即nextval[j] = next[j]

    代码实现如下:

    void NextvalProces(void)
    {
        char str[] = " ababax";//str[0]不放待匹配字符,空格起占位作用
    	int i = 1, j = 0;
    	int n = strlen(str);
    	int *next = (int *)calloc(n, sizeof(int));
    	int *nextval = (int *)calloc(n, sizeof(int));
    	while (i < n - 1)
    	{
    		if (j == 0 || str[i] == str[j])
    		{
    			++i, ++j;
    			next[i] = j;
    		}
    		else j = next[j];//若字符不相同,则j值回溯
    	}
        //输出next[]数组(从数组下标1开始)
    	for (i = 1; i < n; i++)
    		printf("%2d ", next[i]);
    	i = 1, j = 0;
    	while (i < n - 1)
    	{
    		if (j == 0 || str[i] == str[j])
    		{
    			++i;
    			++j;
    			if (str[i] != str[j])
    				nextval[i] = j;
    			else
    				nextval[i] = nextval[j];
    		}
    		else
    			j = nextval[j];
    	}
        //输出nextval[]数组(从数组下标1开始)
    	for (i = 1; i < n ; i++)
    		printf("%2d ", nextval[i]);
    	printf("\n");
        
        return}
    

    2)第二种方法与我的上一篇博客做法相关,那里可能讲的更详细,这里给出链接:
    KMP模式匹配算法(两种)
    处理next[]数组从0开始存放,即子串str[]从0开始,得到的nextval[]也是从0开始,查找时与next[]数组从1开始略有不同,还是以str[] = "ababax"为例

    就是利用未成熟前缀(prefix)表,将我们用maxl[]数组代替未成熟前缀(prefix)表的称呼,有兴趣可以翻阅上一篇,这里给出maxl[]数组的求法,事实上maxl[] = 未成熟prefix[] 在移位处理、首项(未成熟prefix[0])处理即让未成熟prefix[0] = -1后,得到成熟的prefix[]数组,也就是我们说的真正意义上的前缀表(即prefix[]数组),然后令prefix[i] = prefix[i]+1, i >=0可得到从0开始存放数值的next[]数组,这就使maxl[]与未成熟prefix[]与prefix[]与从0开始的next[]关系,也是我讨论的第二种情况

    为了方便,这里直接给出从0开始的maxl[]数组和next[]数组,

    maxl[0~5] = 0, 0, 1, 1, 2, 3

    next[0~5] = 0, 1, 1, 2, 3, 4

    推导nextval[]:nextval[0~5],如果maxl[i] == next[i],则nextval[i] = nextval[i-1],如果maxl[i] == next[i],nextval[i] = next[i]; i 从1开始即i >= 1;

    代码实现如下:

    void Nextval_Proces(void)
    {
        char str[] = "ababax";
    	int i = 1, j = 0, t = 0;
    	int n = strlen(str)
    	int *maxl = (int *)calloc(n, sizeof(int));
    	int *next = (int *)calloc(n, sizeof(int));
    	int *nextval = (int *)calloc(n, sizeof(int));
    	while (i < n)
    	{
    		if (str[i] == str[j])
    		{
    			len++;
    			maxl[i] = j;
    			i++;
    		}
    		else
    		{
    			if (j > 0) j = maxl[j - 1];
    			else
    			{
    				maxl[i] = j;
    				i++;
    			}
    		}
    	}
    	for (i = 0; i < N; i++)
    		printf("%2d ", maxl[i]);
    	putchar('\n');
    	next[0] = 0;//代替了将next[0] = -1, 再+1的繁琐过程
    	for (i = 1; i < n; i ++)
    	    next[i] = maxl[i - 1] + 1;
    	for (i = 0; i < n; i++)
    		printf("%2d ", next[i]);
    	putchar(10);
    	nextval[0] = 0;
    	for (i = 1; i < n; i ++)
    	{
    		if (maxl[i] == next[i])
    		{
    			t = maxl[i];
    			nextval[i] = nextval[t - 1];
    		}
    		else
    			nextval[i] = next[i];
    	}
        for (i = 0; i < n; i++)
    		printf("%2d ", nextval[i]);
    	putchar(10);
    	 
    	return;
    }
    

    二、KMP模式匹配查找改进后的匹配查找

    与上面两种next[]数组或者说nextval[]数组对应的两种查找

    1)从1开始的next[]/nextval[]的匹配查找:

    void KmpSearch(void)
    {
    	char text[] = " ababaxjcashababcjsababcsooababcoidshiababv ababaxjcababaxlkdababclkcjkaababax";
    	char str[] = " ababax";//text[]数组和str[]数组都是从1开始
    
    	int i = 1, j = 0;
    	int n = strlen(str);
    	int *next = (int *)calloc(n, sizeof(int));
    	int *nextval = (int *)calloc(n, sizeof(int));
    	nextval[0] = -1;
        while (i < n - 1)
    	{
    		if (j == 0 || str[i] == str[j])
    		{
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else
    			j = next[j];//若字符不相同,则j值回溯
    	}
    	//输出next[]数组(从1开始)
    	for (i = 1; i < n; i++)
    		printf("%2d ", next[i]);
    	printf("\n");
    	//下面对next[]数组进行处理得到从1开始的nextval[]数组
    	i = 1, j = 0;
    	while (i < n - 1)
    	{
    		if (j == 0 || str[i] == str[j])
    		{
    			++i;
    			++j;
    			if (str[i] != str[j])
    				nextval[i] = j;
    			else
    				nextval[i] = nextval[j];
    		}
    		else
    			j = nextval[j];
    	}
    	//输出nextval[]数组(从1开始)
    	for (i = 1; i < n; i++)
    		printf("%2d ", nextval[i]);
    	printf("\n");
    	j = 1, i = 1;
        while (i < m)
        {
    		if (j == n - 1 && text[i] == str[j])
    		{
    			printf("Found at %d !\n", i - j + 1);
    			j = 0;
    		}
    		if (j == 0 || text[i] == str[j])
    		{
    			++i;
    			++j;
    		}
    		else
    			j = nextval[j];
    	}
    	
    	return;
    }
    

    2)从0开始的next[]/nextval[]的匹配查找:

    void KmpSearch(void)
    {
    	char text[] = "ababaxjcash ababaxjcababaxlkdababclkcjkaababax";
    	char str[] = "ababax";
    	int i = 1, j = 0, t = 0;
    	int n = strlen(str);
    	int m = strlen(text);
    	int *maxl = (int *)calloc(n, sizeof(int));
    	int *next = (int *)calloc(n, sizeof(int));
    	int *nextval = (int *)calloc(n, sizeof(int));
        //计算maxl[]数组
    	while (i < n)
    	{
    		if (str[i] == str[j])
    		{
    			j++;
    			maxl[i] = j;
    			i++;
    		}
    		else
    		{
    			if (j > 0) j = maxl[j - 1];
    			else
    			{
    				maxl[i] = j;
    				i++;
    			}
    		}
    	}
    	//输出maxl[]数组
    	for (i = 0; i < n; i++)
    		printf("%2d ", maxl[i]);
    	putchar(10);
    	//处理maxl[]数组,得到next[]数组
    	next[0] = 0;
    	for (i = 1; i < n; i ++)
    	    next[i] = maxl[i - 1] + 1;
    	//输出next[]数组
    	for (i = 0; i < n; i++)
    		printf("%2d ", next[i]);
    	putchar(10);
    	//处理next[]数组,得到nextval[]数组
    	nextval[0] = 0;
    	for (i = 1; i < n; i ++)
    	{
    		if (maxl[i] == next[i])
    		{
    			t = maxl[i];
    			nextval[i] = nextval[t - 1];
    		}
    		else
    			nextval[i] = next[i];
    	}
    	//输出nextval[]数组
    	for (i = 0; i < n; i++)
    		printf("%2d ", nextval[i]);
    	putchar(10);
    	//进行kmp模式匹配查找
    	j = 0, i = 0;
    	while (i < m)
    	{
    		if (j == n - 1 && text[i] == str[j])
    		{
    			printf("Found at %d !\n", i - j + 1);
    			++i;
    			j = 0;
    		}
    		if (text[i] == str[j]) ++i, ++j;
    		else
    		{
    			if (j == 0) ++i;
    			else j = next[j - 1];
    		}
    	}
    
    	return;
    }
    

    就说那么多,如有错误,多多指正,不胜感激!

    谢谢!再见

    展开全文
  • KMP算法匹配过程示例   第一趟匹配:   a b a b c a b c a c b a b            a b c a c   第二趟匹配:   a b a b c a b c a c b a b              a b c a c   第三趟匹配: ...
  • nextval数组求解

    千次阅读 2020-05-20 17:57:37
    nextval数组求解过程为什么用nextval数组nextval数组求解方式一、模式串的下标从0开始,nextval数组求解方式详解:代码实现二、模式串的下标从1开始,nextval数组求解方式详解:代码实现 为什么用nextval数组 next...
  • 其实计算next的值本身也就是对模式串进行模式匹配,我们一起看看计算next的值的过程; 当模式串 P=“ababcabaababb” 时计算它的next值。 比如: 代码: void get_next(m_1 A) { int i=-1,j=0; A-&...
  • if(j>len_t)//表示t串匹配成功 return i-len_t; else return 0; } int kmp_nextval(char *s,char *t,int pos) { int nextval[105]; memset(nextval,0,sizeof(nextval)); get_nextval(t,nextval); int i=pos;...
  • 数据结构课本上给了这么一段算法求nextval9[]数组 1 int get_nextval(SString T,int &nextval[ ]) 2 { 3 //求模式串T的next函数修正值并存入数组nextval。 4 i=1; nextval[1]=0; j=0; 5 while(i&...
  • nextval数组是对next数组的改进,有这么个循序渐进的过程,所以先从next数组说起。我们都知道:next数组是表征模式串p自身的匹配程度的,所以我们先从一个串的前缀和后缀表达式说起。 串 ...
  • void GetNextval(SqString t, int nextval[]) //对模式串t求nextval[]值 { int j = 0, k = -1; nextval[0] = -1; while (j) { if (k == -1 || t.data[j] == t.data[k]) { j++; k++; if (t.data[j] != t.data...
  • 设字符串S=‘aabaabaabaac',P=‘aabaac' (1)给出S和P的next值和nextval值; (2)若S作主串,P作模式串,试分别写出利用BF算法和KMP算法的匹配过程。 【MOOC答案】
  • KMP之nextval推导

    2016-08-26 18:42:36
    KMP字符串匹配算法的本质呢就是分析子串自身的特点来优化算法。第一个特点 前缀与后缀来自《算法导论》的一个实例 图a 文本 T , 与子串 P,已经匹配成功的q=5个字符,现在第六个字符匹配失败,要将子串P向前...
  • Next 值与 Nextval 值的计算

    万次阅读 多人点赞 2018-05-20 20:42:05
    KMP算法对模式串求解其Next值和Nextval值的计算方法 Next值的计算 方法一 方法二 Nextval值的计算 模式串S = “abaabcac” ,求其 Next 数值序列: 1 2 3 4 5 6 7 8 a b a a b...
  • nextval值是对next值的一种修正,因为在naxt的匹配过程中会出现一定的浪费。 计算nextval和next的方法如下介绍 方法:引入了一个maxL,在计算nextval时,比较方便 写好序号,从1开始 maxL:首个为0,计算包括当前...
  • 求next数组nextval

    千次阅读 2017-06-12 15:52:42
    模式串‘aaaab’和‘adabbadada’ next和nextval数组值 记得大学时自己也总结出了这种算法的,手动计算,数据结构的书都丢了,还好在网上找会了同样的算法 特记下: int get_nextval(SString T,int...
  • KMP算法 next数组 nextval数组

    千次阅读 2020-02-20 20:55:49
    文章目录KMP算法简介KMP算法过程next数组的定义及实现next数组实现代码next数组的改进KMP算法的代码实现 KMP算法简介 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它...
  • KMP算法中next和nextval数组的求解

    千次阅读 多人点赞 2014-10-08 17:04:38
    intget_nextval(SString T,int &nextval[ ]){ //求模式串T的next函数修正值并存入数组nextval。 i=1;nextval[1]=0; j=0; while(i if(j==0||T[i]==T[j]){ ++i;++j; if(T[i]!=T[j]) nextval[i]=j; elsenextval...
  • KMP算法中next与nextval的实现原理

    千次阅读 2018-10-26 13:31:54
    KMP算法中next与nextval的实现原理 最近学习KMP算法,在next数组以及nextval数组的理解上下了好大的功夫,才得以理解。 仅作为备忘以及参考作用,在...next,nextval数组是为了实现不同于朴素模式匹配算法(Brute-Fo...
  • KMP算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的,因此人们称它为克努特——莫里斯——普拉特算法(简称为KMP算法)。此算法可以在O(m+n)的时间数量级上完成串的模式匹配操作。
  • KMP算法是为了优化朴素匹配模式中的主串指针回溯问题,此过程中回产生一个next[i]数组,而KMP优化算法是优化模式串指针的回溯问题,此过程中回产生一个nextval[i]数组。 二 KMP算法之数组之next[i] 当模式串中的第...
  • KMP 算法 手工求解 next 数组,nextval数组 ...设主串 T=“abaabaabcabaabc”,模式串 S=“abaabc”,采用 KMP 算法进行模式匹配,到匹配成功时为止,在 匹配过程中进行的单个字符间的比较次数是? 解答 ...
  • KMP算法使用next数组回溯模式串的过程中还存在一些效率缺陷,其中还有一些无效的比较操作,该算法还能再优化,引进nextval数组,利用next数组求出nextval数组,利用nextval数组实现回溯模式串可以减少无效比较操作。...
  • KMP改进(nextval

    2019-09-22 01:44:20
    这个过程有点长啊,请大家耐心往下看,(我打出来时间更长。。。。) S a (bcabdabcabcd) ab (cabdabcabcd) abc (abdabcabcd) abca (bdabcabcd) abcab (dabcabcd) abcab d (abcabcd) P  a (bcabcd) ab ...
  • 但是KMP对指示主串的指针不必回溯,整个匹配过程对主串只用扫描一次,这对处理从外设输入的庞大文件很有效,可以边读入边匹配,无需重头读,效率很高。   PS:不懂KMP算法基本过程的可以先读一下我的另一篇博客 ...
  • KMP算法中计算next值和nextval的值

    千次阅读 多人点赞 2019-12-27 18:22:50
    书上关于next和nextval的修正值方法比较难理解,所以我这里讲解自己的方法。这里我就不介绍关于字符串匹配中KMP的优点,也不强调next的修正值比next的值好在哪,我们就说方法就行了。 一、next求解。 来,首先给...
  • kmp算法之nextval(转载 )

    千次阅读 2010-10-13 11:29:00
    kmp算法之nextval(转载 )
  • 数据结构中串涉及的内容即串的模式匹配,比较难理解的KMP算法,难在next函数值和nextval函数值的求解 一、问题描述 给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置...

空空如也

空空如也

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

nextval匹配过程