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

KMP算法是一种字符串匹配算法，用于在给定的主串t中查找子串s。其核心思想是利用一个辅助数组next来优化匹配过程。在C代码中，有几个关键的步骤和判断条件需要填充。

（1）在kmp函数中，while循环的条件是确保主串t和模式串s都还有字符需要比较，即j < ls。这是因为当j等于ls时，表示模式串s已经完全匹配完毕。

（2）当主串t的第i个字符与模式串s的第j个字符匹配时，即t[i] == s[j]，可以继续比较下一个字符。这是KMP算法的基本匹配过程。

（3）当主串t的第i个字符与模式串s的第j个字符不匹配时，需要利用next数组进行优化。此时应该将模式串向右移动到next数组指定的位置，即执行j = next[j]。这是KMP算法的核心优化部分。

（4）如果模式串s完全匹配主串t，即所有字符都已经比较完毕，则返回模式串s在主串t中的位置。这个位置是从匹配的起始位置开始计数的，因此返回的是i + 1 - ls。这里的i是主串t的当前比较位置，ls是模式串s的长度。