###INPUT FORMAT

Two line contains two strings, first the target source string, second the pattern string.

####Example Input

abcabcabcd
abcabcd

###OUTPUT FORMAT

One line contains an integer, which points the position of the first letter which matches or -1 if not found.

####Example Output

3

###The Source Code

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

int KMP(string str, string pat);

int main() {
	ofstream fout("KMP.out");
	ifstream fin("KMP.in");
	string str, pat;
	
	fin >> str >> pat;
	fout << KMP(str, pat) << endl;
	return 0;
	}

int KMP(string str, string pat) {
	int i=0, j;
	int len = str.length();
	int size = pat.length();
	int *f= new int[size];
	f[0] = -1;
	for(j=1; j<size; j++) {
		int u=f[j-1];
		while(pat[j]!=pat[u+1]&&u>=0) u=f[u];
		if(pat[j]==pat[u+1]) f[j]=u+1;
		else f[j]=-1;
	}
	j=0;
	while(i<len && j<size) {
		if (pat[j]==str[i]) { i++; j++; }
		else if(j==0) i++;
		else j=f[j-1]+1;
	}
	delete[] f;
	if(j<size) return -1;
	else return i-j;
}