KMP算法计算next数组 匹配字符串

1.概念

     KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

    设主串（ 称作S）为： ssasdsaaasdfsababaaabaasedfcv    模式串（ 称作T）为： ababaaaba用暴力算法匹配字符串过程中，我们会把S[0] 跟 T[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。

    KMP算法的核心是 减少不比要的回溯，问题由模式串决定，不是有主串决定。

    NEXT数组：当模式匹配串失败时，NEXT数组的元素指导 应该用T串的那个元素 进行下一轮的匹配。

   不多说，代码加注释很详细，以免忘记。

2.代码

//KMP Algorithm to find the Next Array and  begining index of matched position

#include 
#include 

typedef char* String ;

//获取 模式字符串T 的 next数组
void get_next(String T, int *next)
{
	int j = 0;                //前缀索引
	int i = 1;                //后缀索引
	next[1] = 0;              //next数组第一个元素都为0
	while (i < T[0])          //一直索引到模式字符串T最后一个元素
	{
		//待判断位置的 的 前缀元素与后缀元素若相同
		if (0 == j || T[i] == T[j])
		{
			i++;              //后移一位 索引后缀元素  
			j++;              //后移一位 索引前缀元素

			//优化 ：加条件 if (T[i] != T[j])...
			//待判断位置的后一位置 的 前缀元素与后缀元素若不相同，不需要回溯，直接确定next元素值
			//实现功能：当子串中有“连续相同字符”失配(与主串不同)时，
			//         直接从这一“连续相同字符”中的第一个字符 进行下一轮对比
			if (T[i] != T[j])
			{
				next[i] = j;  //将j作为next数组对应元素		
			}
			//待判断位置的后一位置 的 前缀元素与后缀元素若相同，通过next数组向前回溯
			else
			{
				next[i] = next[j];
			}
		}
		// 待判断位置的 的 前缀元素与后缀元素若不相同
		else
		{
			j = next[j];      //用next数组 j位置的当前元素 赋值给j,实现向前索引
		}
	}
}

//返回子串T在主串S第pos个字符之后的位置
//若不存在，则返回为0
int Index_KMP(String S, String T, int pos)
{
	int i = pos;
	int j = 1;
	int next[255];
	get_next(T, next);

	while (i