KMP模式匹配算法改进---nextval数组

#include<iostream>
using namespace std;
//nextval数组
void get_nextval(string T,int* nextval)
{
	int i = -1; //指向前缀
	int j = 0; //指向后缀
	nextval[0] = -1;
	while (j < (T.length())-1)
	{
		if (i == -1 || T[i] == T[j])
		{
			i++;
			j++;
            //如果前缀字符与后缀字符不同
			if (T[i] != T[j])
			{
				//当前nextval[j]的值等于i位置的值
				nextval[j] = i;
			}
			else 
			{
				//如果前缀字符与后缀字符相同，则将前缀字符的nextval值赋值给后缀字符的nextval值
				nextval[j] = nextval[i];
			}

		}
		else 
		{
			i= nextval[i];
		}
	}
}
void test()
{
	//测试nextval数组-----------------
	string T = "ababaaaba";
	int nextval[9] = {};
	get_nextval(T, nextval);
	for (int i = 0; i < 9; i++)
	{
		cout << nextval[i] << "  ";
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}

#include<iostream>
using namespace std;
//nextval数组
void get_nextval(string T,int* nextval)
{
	int i = -1; //指向前缀
	int j = 0; //指向后缀
	nextval[0] = -1;
	while (j < (T.length())-1)
	{
		if (i == -1 || T[i] == T[j])
		{
			i++;
			j++;
            //如果前缀字符与后缀字符不同
			if (T[i] != T[j])
			{
				//当前nextval[j]的值等于i位置的值
				nextval[j] = i;
			}
			else 
			{
				//如果前缀字符与后缀字符相同，则将前缀字符的nextval值赋值给后缀字符的nextval值
				nextval[j] = nextval[i]+1;
			}

		}
		else 
		{
			i= nextval[i];
		}
	}
}
//改进KMP改进
int test(string S,string T,int* nextval)
{
	int i =0;//指向主串S
	int j = 0; //指向子串T
	while (i <= S.length() - 1 && j <= T.length() - 1)
	{
		if (j == 0 || S[i] == T[j])
		{
			i++;
			j++;
		}
		else 
		{
			j = nextval[j];
		}
	}
	cout << "i=" << i << endl;
	cout << "j=" << j << endl;
	if (j == T.length())
	{
		return i - j;
	}
	return -1;
}
void test()
{
	string S = "aaaabaaaaaxcdef";
	string T = "aaaaax";
	int nextval[6] = {};
	get_nextval(T, nextval);
	int ret=test(S, T, nextval);
	cout << "子串T在主串S中的起始位置为："<<ret << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}