Manchester-KMP字符串模式匹配算法实现

解题思路:

这个算法不容易理解，不建议花大量时间纠结，对于考研的同学只需要会next手动求法，以及理解kmp算法思想，对于算法思想这里直接照了照片，要更加弄明白的话，可能还需要结合严蔚敏教授的数据结构视频（腾讯视频）

注意事项:

算法中，主串，子串都是从字符数组下标为1的位置开始存储


参考代码:

#include<stdio.h>
#include<string.h>
#include<malloc.h>

typedef struct String_{
 char data[101];/*存放字符串,下标为1表示第一个字符*/
 int length;/*字符串的长度*/

}* string_,STRING;

void get_next(string_ substring,int *next);
int Index_KMP(string_ mainstring,string_ substring,int *next);

int main()
{
    int *next;
  STRING mainstring;
  STRING substring;

     while(scanf("%s",mainstring.data)!=EOF)/*主串输入*/
     {
         scanf("%s",substring.data);/*输入字串*/

         mainstring.length=strlen(mainstring.data);/*求主串长度*/
         substring.length=strlen(substring.data);/*求字符串长度*/

         /*为了求next代码方便，字符串从下标为1开始存放,所以把原字符串依次后移1位*/
          for(int i=substring.length+1;i>0;i--)
            substring.data[i]=substring.data[i-1];/*这样写一次性'\0'也移动*/

          for(int i=mainstring.length+1;i>0;i--)
            mainstring.data[i]=mainstring.data[i-1];/*这样写一次性'\0'也移动*/

           next=(int *)malloc((substring.length+1)*sizeof(int));
           /*为next数组开辟空间,长度比substring多1，因为以下标1为第一个有效元素*/

            int address=Index_KMP(&mainstring,&substring,next);/*求匹配的作弊*/
             printf("%d\n",address);/*输出匹配的位置*/
           free(next);/*释放next空间*/
     }
     return 0;
}
/*---------------------------------------------------------*/
void get_next(string_ substring,int *next)
{
    int i=1,j=0;
    next[1]=0;/*第一个字符发生不匹配，赋值为0表示这种特殊情况*/
     while(i<substring->length)
     {
         if(j==0||substring->data[i]==substring->data[j])
         {
             ++i;
             ++j;
             next[i]=j;
         }
         else
            j=next[j];
     }
}
/*---------------------------------------------------------*/
int Index_KMP(string_ mainstring,string_ substring,int *next)
{
    int i=1;
    int j=1;
    get_next(substring,next);/*获取next*/
     while(i<=mainstring->length&&j<=substring->length)
     {
          if(j==0||mainstring->data[i]==substring->data[j])
          {
              ++i;
              ++j;
          }
          else
            j=next[j];
     }
       if(j>substring->length)
         return i-substring->length;
       else
        return 0;
}

别忘点赞哦-.-