首页 > 试题广场 >

在KMP算法中,已知模式串为ADABCADADA,请写出模式

[单选题]
在KMP算法中,已知模式串为ADABCADADA,请写出模式串的next数组值?
  • 0,1,1,2,1,1,2,3,4,3
  • 0,1,1,1,2,1,2,3,4,3
  • 2,1,1,2,1,1,2,3,3,4
  • 1,2,3,2,1,1,2,4,4,3
推荐
KMP算法:分为模式串和主串,在主串中匹配模式串,next数组中每个值如举例 下标为 j 的值 k,表示模式串第 j 个字符和主串的某个字符没有匹配成功,此时主串这个字符应该和模式串中第 k 个字符进行匹配。
     原理其实就是在第 j 个字符匹配不成功的时候,查找前面会不会出现在第一个字符开始的连续的 k-1个字符和以第 j-1 个字符结束的连续 k-1个字符是相同的情况,如果有的话,我们就可以让模式串从第 k 个字符开始和那个主串中没有匹配成功的字符进行匹配,节省了时间。原因在于在第 j 个字符前面,主串和模式串是匹配成功的,证明在主串中 第一个字符开始的连续的 k-1个字符和第j-1字符结束的连续的k-1个字符是相同的。因此我们是可以看到模式串中第j-1个字符结束的连续k-1个字符和主串中第一个字符开始的k-1个字符是一定相同的,就无需匹配了,我们就只需要从模式串中的第k个字符开始和主串中前面没有匹配成功的该字符进行匹配。
从图上看应该是这样的:

在没有上述情况发生的时候,证明只能从模式串的第一个开始和主串的这个没有匹配成功的字符进行匹配了;还有一种情况就是当k等于1的时候,即之前和这个主串没有匹配成功的字符匹配的模式串字符刚好是从头开始的。那么我们就不能移动字符串只能移动主串了,让主串的下一个字符和模式串的第一个字符开始匹配。

以上的分析转换成模式串的next函数的定义就是:
         next[j] = 0,  当 j = 1 的时候, 理解 :0的含义就是让主串的这个字符和模式串的首字符前面那个不存在的字符进行比较,换种说法就是前面所讲的让主串移动,让主串的下一个字符和模式串的第一个字符进行匹配。
        next[j]  =  Max { k | 1< k < j   且 P 1到 P k-1 == P j-k+1 到 P j-1 |  } 出现上图所示情况
         next[j] = 1  没有上图所示情况,且匹配不成功的模式串字符不是第一个此时需要让主串没有匹配成功的字符和模式串的首字符进行匹配

按上述分析解答:
    A: 首字符  0
    D:前面  A  1
    A :前面 AD      1
    B :前面 ADA   第一个A和第三个A相同,k-1 = 1 ,答案  k = 2 
    C :前面 ADAB  1 
    A :前面 ADABC 1
    D :前面 ADABCA  第一个A和第三个A相同,k-1 = 1 ,答案 k = 2
    A :前面 ADABCAD 前面两个AD和最后两个AD相同, k - 1= 2 ,答案 k = 3
    D :前面ADABCADA 前面三个ADA和最后三个ADA相同, k - 1 = 3 ,答案 k = 4
    A  :前面ADABCADAD 前面 两个AD和最后两个AD相同, k - 1 = 2,答案 k = 3
编辑于 2016-04-22 18:27:19 回复(0)
更多回答
我算出来的是(参考:http://blog.csdn.net/v_july_v/article/details/7041827):
A D A B C A D A D A
-1 0 0 1 0 0 1 2 3 2
但题目的意思好像以0开头,算出来的每项加一,不影响结果。
0 1 1 2 1 1 2 3 4 3
选A
发表于 2015-09-26 18:14:02 回复(4)
在包含Pj ( 0 <= j <= n - 1)的序列中,求出前缀后缀相同的最大长度
a  d  a  b  c  a  d  a  d  a
0  0  1  0  0  1  2  3  2  3
在将该结果向右移动一位,并用-1填充第0位
-1 0  0  1   0  0  1  2  3  2
整体加1
0  1  1  2  1  1  2  3  4  3
因此选择A
发表于 2016-08-23 17:21:12 回复(2)
A
知道KMP的话 这个很简单 只需要计算前面几个就能排除其他选项了
发表于 2015-09-30 21:09:17 回复(0)
答案应该是:(有一样的吗?)

0 0 1 0 0 1 2 3 2 3

发表于 2019-05-20 16:53:14 回复(0)
为什么我算出来是0102102343?
好吧,除了next数组还有一个nextval数组。弄混了。
nextval应该更好吧
编辑于 2015-09-26 23:29:14 回复(2)
选A
A D A B C A D A D A
-1 0 0 1 0 0 1 2 3 2
发表于 2019-10-11 11:55:09 回复(0)
发表于 2018-06-16 17:34:04 回复(0)
自己计算的数值为 -1 0 0 1 0 0 1 2 3 2,看到大家都选A,我也选A
发表于 2017-11-17 19:42:57 回复(0)
A
发表于 2017-11-17 18:37:43 回复(0)
A   答案应该是根据MP算的
发表于 2017-11-16 19:57:03 回复(0)
A
发表于 2017-11-16 15:46:29 回复(0)
选A,我算出来是-1 0 0 1 0 0 1 2 3 2,然后答案是0 1 1 2 1 1 2 3 4 3,可能答案表示的是第几个吧
发表于 2017-11-16 10:38:07 回复(0)
选A,直接可以排除C和D,算到第四位就知道是A不是B了
发表于 2017-11-13 18:11:28 回复(0)
A
发表于 2017-11-13 10:50:05 回复(0)
自己算一下
发表于 2017-08-30 00:04:07 回复(0)
//都是自己写的,求采纳。 //口算也很简单呀,和模式串开始看。
//A假定从开头就匹配失败,规定next【1】=0;
//B然后假定第二位匹配失败,那么显然next【2】=1,如ab,在第二位匹配失败。意味着主///串是a#(#!=b),自然下////一步比较#是否等于a,得next【2】=1;
//C假定第三位匹配失败,而之前的模式串不存在重复。则同B理,next[3]=1;
//如果有重复,如aab,则主串必为aa#(!=b),则只需用模式串中的第2位与主串的#比较///即可,所以next【3】=2;

//这样一直下去。得出所有的next值。

//答案是:0112112343 选A

//用KMP算法写代码当然可以得出Next【j】的值。
//给你贴代码,C的。

#include "stdio.h"
#include "stdlib.h"
#define  MAXSTRLEN  255
typedef unsigned char SString[MAXSTRLEN+1];

void get_next(SString T,int next[]){

   int i=1,j=0;
   next[1]=0;
   while(i<T[0]){
        if(j==0||T[i]==T[j]){
            i++;j++;next[i]=j;
        }else j=next[j];
   }
}
int main(){
    int next[MAXSTRLEN];
    SString S;
    int n,i,j;
    char ch;
    scanf("%d",&n);
    ch=getchar();
    for(i=1;i<=n;i++)
    {
    ch=getchar();
    for(j=1;j<=MAXSTRLEN&&(ch!='\n');j++)
    {
    S[j]=ch;
    ch=getchar();
    }
    S[0]=j-1;    // S[0]用于存储字符串中字符个数
    get_next(S,next);
    printf("NEXT J is:");
    for(j=1;j<=S[0];j++)
    printf("%d",next[j]);
    printf("\n");
    }
    return 0;
}





编辑于 2016-04-26 16:41:27 回复(0)
取多弃少法,可得A。
发表于 2015-09-30 17:04:42 回复(0)
只要掌握好方法,求next太easy啦。直接口算。 第一位为0 第二位为1 第三位看前两位前缀和后缀最长长度,为0,加1后为1 第四位看前三位前缀和后缀最长长度,为1,加1后为2 依次类推。
发表于 2015-09-29 23:50:35 回复(1)
这个 next数组不是MP算法的吗? KMP的话,要看 strict border的
发表于 2015-09-28 10:26:35 回复(0)