Problem Description
给定两个字符串string1和string2，判断string2是否为string1的子串。
Input
输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。
Output
对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
char ca[1000010],cb[1000010];
int nextt[1000010];
void gnext()
{
int i=0,j=-1;
nextt[0]=-1;
while(cb[i]!='\0')
{
if(j==-1||cb[i]==cb[j])
{
i++;
j++;
nextt[i]=j;
}
else
j=nextt[j];
}
}
void kmp()
{
int i=0,j=0;
int len1=strlen(ca),len2=strlen(cb);
while(i<len1&&j<len2)
{
if(j==-1||ca[i]==cb[j])
{
i++;
j++;
}
else
{
j=nextt[j];
}
}
if(j>=len2)
cout<<i-len2+1<<endl;
else cout<<"-1"<<endl;
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>ca>>cb)
{
gnext();
kmp();
}
return 0;
}