kmpアルゴリズムテンプレート

#include<iostream>
#include<string>
#include<vector>
using namespace std;
void getNext(string &str1,vector<int> &next)
{
	next.resize(str1.size());
	next[0]=-1;
	int i=0,j=-1;
	int lenth=str1.size();
	while(i!=(lenth-1))
	{
		if(j==-1||str1[i]==str1[j])
		{
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
}
int kmp(string &str1,string str2,int index=0)
{
	vector<int> next;
	getNext(str2,next);
	int i=index,j=0;
	int sum=0;
	int lenth1=str1.size();
	int lenth2=str2.size();
	while(i!=(lenth1-1))
	{
		if(j==-1||str1[i]==str2[j])
		{
			++i;
			++j;

		}
		else
			j=next[j];
		if(j==lenth2)
		{
                                sum++;
                                j=0;
		}
	}
	return sum;
}
int main()
{
	string str1,str2;
	cin>>str1>>str2;
	int t=kmp(str1,str2,0);
	cout<<t<<endl;
	return 0;
}