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

Description
给定两个字符串string1和string2，判断string2是否为string1的子串。
Input
输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。
Output
对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。
Sample
Input

abc

a

123456

45

abc

ddd

Output

1

4

-1

Hint

#include<bits/stdc++.h>

using namespace std;
#define maxn 1000010
char s[maxn], p[maxn];
int Next[maxn];
void get_next()
{
   int j = -1, k = 0;
   Next[0] = -1;
   int len = strlen(p);
   while(k < len)
   {
       if(j == -1 || s[j] == s[k])
       {
           j++;
           k++;
           Next[k] = j;
       }
       else j = Next[j];
   }
}

int kmp()
{
   int i = 0, j = 0;
   int slen = strlen(s);
   int plen = strlen(p);
   while(i < slen && j < plen)
   {
       if(j == -1 || s[i] == p[j])
       {
           i++;
           j++;
       }
       else j = Next[j];
   }
   if(j == plen) return i - j + 1;
   else return -1;
}
int main()
{
   while(gets(s))
   {
       gets(p);
       get_next();
       printf("%d\n", kmp());
   }
   return 0;
}