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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem 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

Sample Output

1

4

-1

Hint

Source

cjx

在做KMP的题目之前，推荐先去看一下这篇博客

• （原创）详解KMP算法-孤~影()
  这里详细讲解了KMP的基础，有了基础再应付KMP的题目就简单多了。

#include 
    
     #include 
     
      #include 
      
       int Next[1000050];char s1[1000050],s2[1000050];void get_next()//求next数组。{    int i,j,m;    m = strlen(s2);    i = 0;    j = -1;    Next[0] = -1;    while(i