数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用

Time Limit: 1000MS Memory limit: 65536K

题目描述

给定两个字符串string1和string2，判断string2是否为string1的子串。

输入

 输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。

输出

 对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。

示例输入

abc a 123456 45 abc ddd

示例输出

1 4 -1

#include<bits/stdc++.h>   using namespace std;   int next[1000001];   int len1,len2;   char string1[1000001],string2[1000001];  void kmp(int x,int y)   {       int i=0,j=0;  //初始化，从头开始便利     while(i<x&&j<y)  //遍历完主串或模式串跳出循环     {           if(j==-1||string1[i]==string2[j])           {               i++;             j++;           }           else               j=next[j];       }       if(j>=y)           printf("%d\n",i-j+1);       else           printf("-1\n");   }   void get_next(int len)   {       int i=0;next[0]=-1;int j=-1;//在字符串中第一个字符没有前缀，因此赋予初值-1，（当然如果你是从零开始输入的赋值为0）       //这样得到第二个字符的next值就是0，因为第二个字符也只能回溯到0.       while(i<len)       {           if(j==-1||string2[i]==string2[j])           {               i++;j++;next[i]=j;//这里就是找前缀和后缀字符串长度的最大值，当比较不相等时，就回溯到这个下标的下一个再接着进行比较。           }           else               j=next[j];//如果不相等就回溯的string【j】的位置再接着进行比较。       }   }     int main()   {       while(~scanf("%s%s",string1,string2))       {           len1=strlen(string1); // 存放主串的长度         len2=strlen(string2);  //存放模式串长度         get_next(len2-1);           kmp(len1,len2);       }   }  

转载于:https://www.cnblogs.com/CCCrunner/p/6444628.html