#include"CString.h"

int Index_BF(SString S, SString T, int pos) {
	//返回模式T在主串S中第pos个字符开始第一次出现的位置(从主串pos处开始)。不存在，返回0
	//其中，T非空，1<=pos<=S.length
	int i = pos;
	int j = 1;									//初始化
	while (i <= S.length && j <= T.length)		//两个串均为比较到末尾
	{
		if (S.ch[i] == T.ch[j])
		{
			++i;
			++j;								//继续比较后继字符
		}
		else
		{
			i = i - j + 2;
			j = 1;								//指针后退重新开始匹配
		}
	}
	if (j > T.length)
	{
		return i - T.length;					//匹配成功
	}
	else
	{
		return 0;								//匹配失败
	}
}

void get_next(SString T, int next[]) {
	//求模式串T的next函数值并存入next数组
	int i = 1;
	next[1] = 0;
	int j = 0;
	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			++i; ++j;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}

int Index_KMP(SString S, SString T, int pos, int next[]) {
	//利用模式串T的next数组求T在主串S中的第pos个字符之后的位置
	//其中，T非空，i<=pos<=T.length
	int i = pos;
	int j = 1;
	while (i <= S.length && j <= T.length)			//两个串均未比较到串尾
	{
		if (j == 0 || S.ch[i] == T.ch[j])			//继续比较后继字符
		{
			++i; ++j;
		}
		else
		{
			j = next[j];							//模式串向右移动
		}
	}
	if (j > T.length)
	{
		return i - T.length;						//匹配成功
	}
	else
	{
		return 0;									//匹配失败
	}
}

void get_nextval(SString T, int nextval[]) {
	//求模式串T的next函数修正值并存入数组nextval
	int i = 1;
	nextval[1] = 0;
	int j = 0;
	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			++i; ++j;
			if (T.ch[i] != T.ch[j])
			{
				nextval[i] = j;
			}
			else
			{
				nextval[i] = nextval[j];
			}
		}
		else
		{
			j = nextval[j];
		}
	}
}