Manchester


私信TA

用户名:wenyajie

访问量:16522

签 名:

男孩

排  名 3
经  验 11600
参赛次数 0
文章发表 147
年  龄 0
在职情况
学  校 Qing Dao University
专  业

  自我简介:

干大事,12月26号之后长期回归

TA的其他文章

解题思路:

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

TIM截图20180512203944.png

TIM截图20180512204002.png

TIM截图20180512204025.png

TIM截图20180512204120.png

TIM截图20180512204135.png



注意事项:

算法中,主串,子串都是从字符数组下标为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;
}

别忘点赞哦-.-

  评论区