KMP算法的C++实现

#include
#include
#include
using namespace std;
vector getNext(string str)
{
	if (str.size() == 1)
	{
		return { -1 };
	}
	vectornext(str.size());
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int cn = 0;
	while (i < next.size())
	{
		if (str[i-1] == str[cn])
		{
			next[i++] = ++cn;
		}
		else if (cn > 0)
		{
			cn = next[cn];
		}
		else
		{
			next[i++] = 0;
		}
	}
	return next;
}
int Kmp(string str1, string str2)
{
	if (str2.size() < 1 || str1.size() < str2.size())
	{
		return -1;
	}
	vectornext = getNext(str2);  //调用函数获取next数组
	int p1 = 0;             //定义分别指向str1和str2的指针
	int p2 = 0;
	while (p1 < str1.size() && p2 < str2.size())
	{
		if (str1[p1] == str2[p2])   //如果字符相同，则指针指向下一个字符
		{
			p1++;
			p2++;
		} 
		else if (p2 == 0)           //实在匹配不到
		{
			p1++;
		}
		else
		{
			p2 = next[p2];           
		}
	}
	return p2 == str2.size() ? p1 - p2 : -1;
}

int main()
{
	cout << Kmp("abcabcabd", "abcabd") << endl;
	system("pause");
	return 0;
}