学步园

子串的定位操作通常称作串的模式匹配，是各种处理系统中的最重要操作之一。

模式匹配最朴素的算法是回溯法，即模式串跟主串一个字符一个字符的匹配，当模式串中跟主串不匹配时，主串回溯到与模式串匹配开始的下一个位置，模式串回溯到第一个位置，继续匹配。算法的时间复杂度为O（m*n），算法如下：

//朴素的串的模式匹配算法，S为主串，T为模式串，即找S中有没有与T相同的字串
int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替
{
	int i=pos, j=0; 
	while(i <strlen(S) && j <strlen(T))//确保未超出字符串的长度
	{
		if (S[i] == T[j])
		    { ++i; ++j;} //如果相同，则继续向后比较
		else 
		    {i = i-j+1; j =0;} //如果不同，就回溯，重新查找
	}
	if (j == strlen(T))
		return i-strlen(T); //若匹配成功，返回S中与T字符串相同开始位置的索引
	else return 0; //若匹配不成功，返回0
}

O（m*n）的时间复杂度有点大，于是人们发现了KMP算法，核心思想是：当不匹配发生时，主串不回溯，模式串回溯到“合适”的位置，哪个位置合适，只与模式串有关，所以可以先算出模式串中各个字符，当不匹配发生是，应该回溯到哪个位置。算法整体时间复杂度O(m+m)。

算法如下：

void GetNext(char* T, int *next)
{
	int i=1,j=0; 
	next[1]=0;
	while( i < strlen(T) )
	{ 
		if (j == 0 || T[i] == T[j])
		{
			 ++i; ++j; 
			 next[i] = j;
		} 
		else j = next[j];
	}
} 

int KMP(char* S, char* T, int pos)
{
	int i = pos, j = 1;
	while (i)
	{
		if (S[i] == T[j])
		{ 
			++ i;  ++ j;
		} 
		else 
			j = next[j]; 
	}
	if (j > strlen(T)) 
		return i-T[0];
	else 
		return 0; 
} 

求next的操作不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：

void GetNextEx(char *T, int *next)
{
	int i=1,j=0; next[1] = 0;
	while(i < strlen(T))
	{
		if (j == 0 || T[i] == T[j])
		{
			++i; ++j;
			if (T[i] == T[j])
				next[i] = next[j];  //减少回退次数
			else   next[i] = j;  //和上面算法一样next[i]=j
		}
		else j = next[j]; 
	} 
}