//线性表的使用及函数定义
//KMP算法如果不想了解理论可以看看这个：
//https://blog.csdn.net/weixin_46007276/article/details/104372119?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163490584616780264080014%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=163490584616780264080014&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-104372119.pc_search_result_cache&utm_term=kmp%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187
//KMP算法的详细理论视频我放到b站上了，有兴趣看看。：



#include<stdio.h>
#include<malloc.h>
#define _CRT_SECURE_NO_WARNINGS_
#define OK 2
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define Status int//用数值返回状态，状态值如上所示。
#define ElemType char//串一半都是字符串。
#define InitSize 100
#define IncreaseSize 10 
typedef struct str
{
	ElemType* base;
	int Alllen;
	int CurLen;
}String;

//朴素的模式识别算法。
int MortalIndex(String &S,String &T,int pos)
{
	String temp;
	temp.base = (ElemType*)malloc((T.CurLen) * sizeof(ElemType));
	int i = pos;
	int j = 0;
	for (i = pos; i < S.CurLen ; i++)
	{
		for (j = 0; j < S.CurLen; j++)
		{
			if (S.base[i + j] == T.base[j]) j = j;
			else break;
		}
		if (j == S.CurLen) return i;
	}
	if (i == S.CurLen) return 0;
}//S为目标串，T串为模式串，pos为从第pos位开始进行比较。
//朴素模式匹配算法，其进位为每次加一，会浪费大量的时间。时间复杂度高。回溯次数大，回溯时间长。


//使用CMP算法进行处理
void get_next(String& T, int next[])
{
	int i = 1;//next的下标，从1开始。
	next[i] = 0;
	next[0] = 999999;//随便一个都可以，无所谓的。我只是不想让这个next[0]是空的，不好看。。。。。。
	int k = 0;//k为可以满足条件的最大长度值。
	while (i < T.CurLen)
	{
		if (k == 0 || T.base[i] == T.base[k])
		{
			i++;
			k++;
			next[i] = k;
		}//如果Pj=Pk或着直接为零,那么，直接加一就行了。
		else k = next[k];//当不满足上述条件的时候，直接进行处理，让k取到next【k】。
	}
}
Status Index_CMP(String& S, String& T, int pos)
{
	int* next;
	get_next(T, next);
	int i = pos;
	int k = 1;
	while (i < S.CurLen && k < T.CurLen)
	{
		if (k == 0 || S.base[i] == T.base[k])
		{
			k++;
			i++;
		}//如果为0，那么相当于向后移动一位，如果两个相等，向后移动一位是属于正常的现象。
		else
		{
			k = next[k];//如果匹配失败，直接进入next[k]位置进行匹配与判断。这个时候i是不动的。
		}
	}
	if (k > T.CurLen) return i - T.CurLen;//现在比到了最后一位。要回到第一位并返回第一位的值。
	else return 0;//当k无法大于T串长度时，认为其没有办法完成全部T串的比较。直接失效。
}




int main()
{
	return 0;
}