KMP算法（C语言）

朱雀 2022-11-15 11:46 166阅读 0赞

本着对KMP算法的好奇，特地进行学习一下。

### 文章目录 ###

*  一、简介
 *  二、构建next数组
 *  三、KMP算法的实现

# 一、简介 #

> KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt三位科学家发表的一个模式匹配的算法，这种算法相较于BF（暴力）匹配算法可以大大减少其回溯计算的次数，也就是减少不必要的回溯发生。

> 该算法的核心是要构建一个引导整个匹配过程的next数组，我们可以把这个next数组看做是KMP算法中的回溯控制中心，它会控制匹配过程字符串T的回溯位置。具体的构建过程可以参看《大话数据结构》一书、与视频[【C语言描述】《数据结构和算法》][C]。

# 二、构建next数组 #

构建next数组的关键在于：找到当前字符之前的串的前后缀相同字符的个数。刚一开始有些难以理解这是什么意思，不过看一下代码应该就会好很多。如下所示：

#include<stdio.h>
    typedef char* String;
    
    //获取KMP算法所使用的next数组
    void get_next( String T,int *next)
    { 
    	int i=1,j=0,len;
    	next[1]=0;
    	len=T[0] - '0';
    
    	while( i < len)
    	{ 
    		if(0 == j || T[i] == T[j])
    		{ 
    			i++;
    			j++;
    			next[i]=j;
    			/*if( T[i]!=T[j]) //优化 { next[i]=j; } else { next[i]=next[j]; }*/
    		}
    		else
    		{ 
    			j=next[j];		//要回溯到next[j]位置
    		}
    	}
    }

> 不难看出， 这里的前缀是指：字符串从第一个位置开始的前 j j j\-1（ j ! = 0 j!=0 j!=0）个字符，而后缀则是指字符串从当前位置开始的后 j j j\-1个字符。通过这种记录前后缀相同个数的方式，就可以大大减少匹配过程中的回溯次数。

# 三、KMP算法的实现 #

//返回符合条件的字符串的位置
    int Index_KMP( String S, String T, int pos)
    { 
    	int i=pos,j=1;
    	int next[255];
    	int sLen,tLen;
    
    	get_next(T,next);
    	sLen=S[0]-'0';
    	tLen=T[0]-'0';
    
    	while( i <= sLen && j <= tLen)		//其中一个字符串达到末尾则终止匹配过程
    	{ 
    		if( 0==j || S[i] == T[j] )
    		{ 
    			i++;
    			j++;
    		}
    		else
    		{ 
    			j=next[j];
    		}
    	}
    
    	if( j > tLen )
    	{ 
    		return i-tLen;
    	}
    	else
    	{ 
    		return 0;
    	}
    }
    
    int main()
    { 
    	String S="5abcdex";
    	String T="2cd";
    	int pos=Index_KMP(S,T,0);
    	printf("%d\n",pos);
    	
    	return 0;
    }

执行效果：  
![在这里插入图片描述][20210401153531977.png]

> 参考资料：《大话数据结构》、[【C语言描述】《数据结构和算法》][C]

[C]: https://www.bilibili.com/video/BV1jW411K7yg?p=40&spm_id_from=pageDriver
[20210401153531977.png]: /images/20221022/dc633e7d236e40d7a9142519f7844a61.png