试题三（15分）

阅读下列说明和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 <stdio.h>

#include <stdlib.h>

#include <string.h>

/*求next[]的值*/

void get_next( int *next, char *s, int ls)  {

    int i=0，j=-1;

    next[0]=-1;/*初始化next[0]*/

    while(i < ls){/*还有字符*/

    if(j==-1l ls[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, int lt, int ls )

 {

       Int i= 0,j =0 ;

       while (i < lt &&  （1）   ){

          if( j==-1 ||     （2）  ){

                 i ++ ;

                 j ++ ;

           } else

                      （3）    ;

}

if (j >= ls)

return     （4）   ;

else

    return -1;

}

（6）[-1, -1,1, -1, -1, 2, 0, 0]，

（7）6。

（6）对于字符串"BBABBCAC"，其next数组的元素值求解如下：

• 对于第一个字符’B’，由于没有前一个字符进行比较，所以next[0]的值为-1。
• 对于第二个字符’B’，与第一个字符相同，所以next[1]的值为next[0]的值加1，即-1+1=0，但由于规定next数组的值不能为负数，所以取为-1。之后的字符同理计算，得到next数组的元素值为：-1,-1,1,-1,-1,2,0,0。

（7）对于主串"AABBCBBABBCACCD"和子串"BBABBCAC"，使用KMP算法进行匹配：

• 初始时，i和j都设为0。
• 比较主串和子串的第一个字符，发现相同，所以i和j都加1。此时主串i指向"B"，子串j指向"B"。
• 继续比较，主串的下一个字符是"B"，与子串的当前字符相同，再次增加i和j的值。此时主串i指向第二个"B"，子串j指向第二个"B"。
• 继续比较直到子串的j指向最后一个字符"C"，此时j已经移动了6步，表示子串在主串中的位置是6，所以函数Kmp的返回值是6。