[数据结构与算法]KMP算法（高效改进版）--C++实现

GetNextval的代码如下：

void GetNextval(string t, int nextval[]) {
	int k = -1, j = 0;
	nextval[0] = -1;
	while (j < t.length())
	{
		if (k == -1 || t[j] == t[k]) {
			j++; k++;
			if (t[j] != t[k])
			{
				nextval[j] = k;
			}
			else
			{
				nextval[j] = nextval[k];
			}
		}
		else
		{
			k = nextval[k];
		}
	}

}

KMPIndex1的代码实现部分如下：

int KMPIndex1(string s, string t) {
	int nextval[MaxSize], i = 0,j = 0;
	GetNextval(t, nextval);
	cout << s.length() << "\t" << t.length() << endl;
	while (i < s.length() && j < t.length())
	{
		if (j == -1 || s[i] == t[j]) {
			i++;
			j++;
		}
		else
		{
			j = nextval[j];
		}
		if (j == -1)
		{
			j++; i++;
		}
		cout << "i:" << i << " j:" << j << endl;
	}
	if (j >= t.length())
	{
		return i - t.length();
	}
	else
	{
		return -1;
	}
}

测试部分：

?

?