KMP

Description
给你两个字符串，求第二个串(模式串)在第一个串(母串)中的位置。

Input
两行，两个长度∈[1,1000000]的只含有大小写字母的字符串。

Output
如果能够匹配，输出模式串第一个字母在母串的位置。否则输出0。

Sample Input1
10 2
abaabababa
ba

Sample Output1
2

Sample Input2
10 2
abaabababa
bb

Sample Output2
0

Hint
热烈欢迎Hash的，强烈鄙视输0骗分的。

kmp？？！！

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int i , j , next[1000003];
char a[1000003] , b[1000003] ;


int main() {
//    freopen( "10722.in","r",stdin ) ;
//    freopen( "10722.out","w",stdout ) ;
scanf( "%d%d" ,&i , &j ) ;
scanf( "%s%s" ,b , a ) ;

for( int q = 1 , k = 0 ; q <= j ; ++ q ) {
while( k > 0 && a[q] != a[k] )
k = next[k-1] ;
if( a[q] == a[k] ) ++k ;
next[q] = k ;
}

for ( int x = 0,q = 0; x < i; ++x) {
while(q > 0 && b[x] != a[q])
q = next[q-1];
if ( b[x] == a[q])    q++;
if (q == j)
{
printf("%d
",( x-j+2 ) );
return 0 ;
}
}
printf( "0
" ) ;
return 0;
}