shenwenjie 2020-04-11
AC_Code:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <stack> using namespace std; typedef long long ll; int Nex[1000000]; char st[1000000]; char str[1000000]; void Find_Nex() { int i=0,j=-1; Nex[0]=-1; int len=strlen(str); while( i<len ) { if( j==-1 || str[i]==str[j] ) { i++; j++; Nex[i]=j; } else j=Nex[j]; } } void kmp() { int i=0,j=0; int len1=strlen(st); int len2=strlen(str); while( i<len1&&j<len2 ) { if( j==-1 || str[j]==st[i]) { i++; j++; } else j=Nex[j]; } if( j==len2 ) cout<<i-j+1<<endl; else cout<<"-1"<<endl; } int main() { while(~scanf("%s",st)) { scanf("%s",str); memset(Nex,0,sizeof(Nex)); Find_Nex(); kmp(); } return 0; }