子串匹配 KMP算法

1. 相关概念:

1. 模式字符: 指的其实就是子字符串

2. 算法思想:

1. 可以把字符匹配看作状态的转移, 如果匹配就进入下一状态, 如果不匹配就回溯
   1. 即状态转移由两部分因素决定, 当前状态与输入字符
2. 如果提前预定好了状态转换表, 则匹配过程如下图所示:
3. 所以最主要的工作是根据给定的字串生成对应的状态转换表
   1. 实际上KMP中只有两种状态转换:
   2. 如果输入字符 == 当前状态所代表的字串字符, 则向前推进
   3. 如果输入字符 != 当前状态所代表的字串字符, 则回溯
4. 而其中最重要的就是确定回溯的位置
5. 结论:如下图
   1. 回溯的位置 ⇒ X的下一步
      1. 跳到当前X记录所在状态, 并在此状态下, 按当前枚举的输入字符走一步, 下一步的位置就是回溯状态
      2. 而X记录的位置也是要维护的, 每次枚举完所有的输入字符, X都要在X状态上走一步, 按照最新状态所代表的字串字符来走
6. 直观理解: 经过上述操作, X与j拥有相同的前缀, 且该前缀会尽可能的长
   1. 这样就能缩短回溯距离, 节省时间,
   2. 因为能匹配到j说明j的前缀能够匹配, 所以X的前缀也必定能匹配, 省去从头匹配前缀

3. 在c语言中的实现

梗概:

1. 生成状态转换表:
   1. 第一个状态直接初始化为 字符符合往下走 字符不符合默认跳转到0状态
   2. X初始在0状态
   3. 从第二个状态开始枚举所以可能的输入字符 代码:

int KMPpat(char pat[],int ***dp){
	int len = strlen(pat);
	/*初始化状态转换表*/
	(*dp)=(int**)calloc(len,sizeof(int*));
	for(int j=0;j<len;++j){
		(*dp)[j]=(int*)calloc(256,sizeof(int));
		for(int i=0;i<256;++i)
			(*dp)[j][i]=0;
	}
	if(!*dp)return 0;//申请空间失败
	// dp[当前状态][传入字符]=转跳的状态
	/*初始化X和状态0*/
	(*dp)[0][pat[0]]=1;
	int X=0;
	for(int j=1;j<len;++j){
		for(int c=0;c<256;++c)
			/*传入字符不符合的话都要回溯*/
			(*dp)[j][c]=(*dp)[X][c];
		/*字符符合进入下一检测状态*/
		(*dp)[j][pat[j]]=j+1;
		/*X按当前j转跳状态*/
		X=(*dp)[X][pat[j]];
	}
	return 1;
}
 
int KMPmatch(char pat[],char txt[]){
//以pat为子串匹配txt字符串,成功返回已匹配的开始位置
//无字串返回-1,空间不足返回-2
	int **dp;
	/*根据模式字符串生成对应的匹配状态转换表*/
	if(!KMPpat(pat,&dp))return -2;
	int patlen = strlen(pat);
	int txtlen = strlen(txt);
	int j=0;
	for(int c=0;c < txtlen;++c){
		/*根据dp转换当前匹配检测状态*/
		j=dp[j][txt[c]];
		if(j==patlen){//终点状态,匹配完毕
			for(int i=0;i<patlen;++i)
				free(dp[i]);
			free(dp);
			return c-patlen+1;
		}
	}
	for(int i=0;i<patlen;++i)
		free(dp[i]);
	free(dp);
	return -1;
}