在KMP算法中，计算模式串的next时，当j=0时，为什么要取next[0]=-1？
在KMP算法中，计算模式串的next时，当j=0时，为什么要取next[0]=-1？
参考答案和解析
当模式串中 0 号字符与主串中某字符比较不等时,此时 next[0]= - 1 表示模式串中已没有字符可与主串中的当前字符比较,主串当前指针应后移至下一个字符,再和模式串的 0 号字符进行比较。
相关考题：
以下程序的输出结果是 ______。 Dim n(2,2), i, j As Integer For i = 0 To 2 For j = 0 To 2 n(i,j) = i + j Next j Next i For i = 0 To 1 For j = 0 To 1 n(i+ 1 ,j + 1) = n(i + 1,j + 1) + n(i, j) Next j Next i Print n(i, j)A．14B．0C．6D．值不确定
在KMP算法中，已知模式串为ADABCADADA，请写出模式串的next数组值()A.0,1,1,2,1,1,2,3,4,3B.1,2,3,2,1,1,2,4,4,3C.0,1,1,1,2,1,2,3,4,3D.2,1,1,2,1,1,2,3,3,4
已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i和j的值分别是()。A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=2
下列程序段的执行结果为______。 K=0 For J = 1 To 2 For I = 1 To 3 K=I+1 Next I For I = 1 To 7 K=K+1 Next I Next J Print KA． 10B．6C．11D．16
有下面的程序段，其功能是按图1所示的规律输出数据： Dim a(3，5)As Integer For i=1 To 3 For j=1 To 5 a(i，j)=i+j Print a(i，j)； Next Print Next若要按图2所示的规律继续输出数据，则接在上述程序段后面的程序段应该是（ ）。A.For i=1 To 5 For j=1 To 3 Print a(j，i)； Next Print NextB.For i=1 T0 3 For j=1 To 5 Print a(j，i)； Next Print NextC.For j=l To 5 For i=1 To 3 Print a(j，i)； Next Print NextD.For i=1 To 5 For=1 To 3 Print a(i，j)： Next Print Next
●在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下（其中，j为模式串中字符的序号）。对于模式串“abaabaca”，其next函数值序列为(57)。(57)A. 01111111B.01122341C.01234567D.01122334
下面的算法是计算不带节点的单链表长度，其中能正确执行的是______。A．Function Length(L：Link) integer begin p:=L； j:=0； while p↑.next≠NIL DO [p：=p↑.next； j：=j+1 ] return(j) end;B．Function Length(L：Link) integer begin p：=L； k：=0； while p≠NIL DO [p：=p↑.next； k：=k+1) return(k) end；C．Function Length(L：Link)integer begin p：=L；k：=0； repeat k：=k+1； p=p↑.next until p=NIL return(k-1) end；D．Function Length(L：Link)integer begin p：=L↑.next； k：=1； while p≠NIL DO [k：=k+1； p：=p↑.next] return(k) end；
下列程序执行后，执行的结果是______ 。 Dim M(2) For i = 1 To 2 M(i) = 0 Next i k=2 For i = 1 To k For j = 1 To k M(j) = M(i) + 1 Print M(k): Next j Next IA．1234B．0123C．223D．2345
当Form_Click;事件发生时,窗体上显示的第三行是 ______。 Private Sub Form_Click() Dim i As Integer, j As Integer, k As Integer Dim x(5, 5) As Integer For i = 1 To 5 k = 1 For j = 1 To 5 If i ＜= j Then x(i, j) = k + 1 k=k+2 Else x(i, j) = k + 1 End If Next j Next i For i = 1 To 5 For j = 1 To 5 Print x(i, j) Next j Print Next i End SubA．22135B．21357C．22213D．13579
程序代码如下，当单击窗体上的Command1控件时，在窗体上输出的结果是( )。 Private Sub Command1_Click() Dim aa(3，3)As Integer Dim i As Integer,j As Integer Dim s As Integer For i=0 To 3 For j=0 To 3 aa(i，j)=i*4+j+1 Next j Next i For i=0 To 3 s=s+aa(i，1) Next i Print s End SubA．32B．28C．30D．36
在窗体中添加1个命令按钮(其Name属性为Command1)和1个标签(其Name属性为Lable1)，然后编写如下代码： Private Sub Commandl_Cliek() Dim arrayl(10, 10)As Integer Dim i, j, Sum AsInteger Sum＝0 For i=1 To 10 Forj=1 To 10 arrayl(i, j)=i+j Nextj Next i End Sub 此程序的功能是求数组arrayl主对角线元素的和，并把结果显示在标签中，为实现此功能，省略号处的程序段应该是 ( )A．For i=1 To 10 For j=1 To 10 If i=j Then Sum = Sum+ arrayl (i,j) End If Next j Next i Labelt. Caption=SumB．For i=l TO 10 Forj=1 To 10 If i= =j Then Sum=Sum+array1 (i,j) End If Next j Next i Labell. Caption=SumC．For i=1 To 10 For j=1 To l0 If i=j Then Sum=Sum+arrayl (i,j) End If Next i Next j Lahell. Caption=SumD．For i=1 To 10 For j=1 To l0 If i=j Then Sum=arrayl (i,j) End If Next j Next i Labell. Caption=Sum
下列程序段的执行结果为_______。 N=0 For I=1 To 3 For J=5 To 1 Step -1 N=N+1 Next J Next I Print N；J；IA．12 0 4B．15 0 4C．12 3 1D．15 3 1
当Form1_Click事件发生时，窗体上显示的第三行是( )。 Dim i As Integer，j As Integer，a(5，5) As Integer For i=1 To 5 For j=1 To 5 If(i＜=j)Then a(i,j)=1 Else a(i,j)=0 End If Next j Next i For i=1 To 5 For j=1 To 5 Print a(i,j), Next j Print Next i End SubA．0 0 0 1 1B．0 0 1 1 1C．0 1 1 1 1D．1 1 1 1 1
阅读下面的程序段： a==0 For i=1 To 3 For j=1 To i For k=j To 3 a=a+l Next k Next j Next i 执行上面的程序段后，a的值为（ ）。A.3B.9C.14D.21
编写以下程序段： DIM I, J, K, A A=0 FOR I = 1 TO 3 FOR J = 1 TO I FOR K=-J TO 3 A=A+1 NEXT K NEXT J NEXT I 执行上面的三重循环后，变量A的值为( )。A．3B．9C．14D．21
试题四（共15分）阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1 。KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：1．在串t和串s中，分别设比较的起始下标i=J=O2．如果串t和串s都还有字符，则循环执行下列操作：（1）如果j=-l或者t[i]-s[j]，则将i和j分别加1，继续比较t和s的下一个字符；（2）否则，将j向右滑动到next[j]的位置，即j =next[J]3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回一1．其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。【C代码】（1）常量和变量说明t，s：长度为悯铂Is的字符串next:next数组，长度为Is（2）C程序include stdio．hnclude stdliB．hinclude string．h／*求next【】的值*/void get_next（ int *next, char *s, int Is） {int i=0，j=-1；next[0]=-1；/*初始化next[0]*／while（i ils）{/*还有字符*／if（j=-1l ls[i]=s[j]）{／*匹配*／j++；i++；if（ s[i]一s[jl）next [i]- next[j];elseNext[i]=j；}elseJ= next[j]；}}int kmp（ int *next, char *t ,char *s, int.lt, int Is ）{inti= 0,j =0 ;while （ilt （ 1 ） {if（ j=-1 II 2_） {i++ ;j ++ ;} else（3） :}if （j= ls）Retum （4）else .retum-1；【问题1】（8分）根据题干说明，填充C代码中的空（1）～（4）.【问题2】（2分）根据题干说明和C代码，分析出kmp算法的时间复杂度为 （5）(主串和子的长度分别为It和Is，用O符号表示）。【问题3】（5分）根据C代码，字符串“BBABBCAC”的next数组元素值为 （6） (直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC则函数Kmp的返回值是 （7）
在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为 (60) 。A.01234B.01122C.01211D.01111
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：1．在串t和串s中，分别设比较的起始下标i=j=0。2．如果串t和串s都还有字符，则循环执行下列操作：（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；（2）否则，将j向右滑动到next[j]的位置，即j =next[j]。3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1。其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。【C代码】（1）常量和变量说明t，s：长度为lt和ls的字符串next:next数组，长度为ls（2）C程序#include #include#include/*求next[]的值*/void get_next( int*next, char *s, int ls) { inti=0，j=-1; next[0]=-1;/*初始化next[0]*/ while(i= ls)return （4） ;else return-1;}【问题1】（8分）根据题干说明，填充C代码中的空（1）～（4）.【问题2】（2分）根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。【问题3】（5分）根据C代码，字符串"BBABBCAC"的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为"AABBCBBABBCACCD"，子串为"BBABBCAC"，则函数Kmp的返回值是（7）。
在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为"abaac"，则其next函数值为 （ ） 。A.01234B.01122C.01211D.01111
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】 模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1 。 KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下： 1．在串t和串s中，分别设比较的起始下标i=j=0。 2．如果串t和串s都还有字符，则循环执行下列操作： （1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符； （2）否则，将j向右滑动到next[j]的位置，即j =next[j]。 3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1． 其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。【C代码】（1）常量和变量说明 t，s：长度为悯铂Is的字符串 next:next数组，长度为Is（2）C程序#include #include #include /*求next[]的值*/void get_next( int *next, char *s, int Is) { int i=0，j=-1; next[0]=-1;/*初始化next[0]*/ while(i if(j==-1lls[i]==s[j]){/*匹配*/ j++; i++; if( s[i]==s[j]) next[i]= next[j]; else Next[i]= j; }else j = next[j]; }} int kmp( int *next, char *t ,char *s, intlt, int Is ) { Int i=0,j =0 ; while(i if(j==-1 || （2） ){ i++ ; j++ ; }else （3） ;}if (j >= ls)return （4） ;else return -1;} 【问题1】（8分） 根据题干说明，填充C代码中的空（1）～（4）.【问题2】（2分）根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。【问题3】（5分）根据C代码，字符串“BBABBCAC”的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC”，则函数Kmp的返回值是（7）。
函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q; int j; p=L;j=0; while(( （1） )(jnext;j++; } if(p-next==NULL||ji-1) return ERROR; q=p-next; （2） ; *s=q-data; free(q); return OK;}/*listDelete*/
填空题函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q; int j; p=L;j=0; while(( （1） )(jnext;j++; } if(p-next==NULL||ji-1) return ERROR; q=p-next; （2） ; *s=q-data; free(q); return OK;}/*listDelete*/
判断题KMP算法的特点是在模式匹配时指示主串的指针不会回溯。A对B错