试题三（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;

}

（1）：j<ls;

    （2）：t[i]==s[j];

    （3）：get_next(next, s, ls);

            j=next[j];

    （4）：i+1-ls;

（1）在KMP算法中，循环继续的条件是主串t还有字符未比较完并且子串s的当前位置j未超出其长度，即 j < ls。所以空（1）应填写 j < ls。

（2）在KMP算法中，如果当前字符匹配成功，即 t[i] == s[j]，则主串t和子串s的指针都向前移动一位。所以空（2）应填写 t[i] == s[j]。

（3）如果当前字符匹配失败，即 t[i] != s[j]，我们需要根据next数组将子串s的指针移动到正确的位置以继续匹配。因此，空（3）应填写调用get_next函数更新j的值，即 j = next[j]。

（4）如果子串s的所有字符都已经成功匹配完，即 j >= ls，那么返回子串s在t中的位置。这个位置是从1开始计数的，所以应返回的是从当前主串t的起始位置i开始到子串s结束位置的偏移量，即 i - ls + 1。所以空（4）应填写 i - ls + 1。