Manchester-KMP算法中的模式串移动数组

解题思路:

看图截手动实现过程：

注意事项：

原字符串，以及next[]数组，规定以下标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);
void out_put(int *next,int length);

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

     while(gets(substring.data)!=NULL)
     {
         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'也移动*/
            
           next=(int *)malloc((substring.length+1)*sizeof(int));
           /*为next数组开辟空间,长度比substring多1，因为以下标1为第一个有效元素*/

           get_next(&substring,next);/*获取next*/
           out_put(next,substring.length);/*输出next内容*/
           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];
     }
}
/*---------------------------------------------------------*/
void out_put(int *next,int length)
{
    for(int i=1;i<length;i++)/*第一个有效元素下标为1*/
      printf("%d ",next[i]);
      printf("%d\n",next[length]);
}

别玩点赞哦-.-