KMP模式匹配算法

布满荆棘的人生 2022-03-11 15:59 220阅读 0赞

## 1、前缀和后缀 ##

前缀指除了最后一个字符以外，一个字符串的全部头部组合，如：对于字符串”ababa”，它的前缀集合为\{”a”, ”ab”, ”aba”, ”abab”\}。

后缀指除了第一个字符以外，一个字符串的全部尾部组合，对于字符串”ababa”，它的后缀集合为\{”baba”, ”aba”, ”ba”, ”a”\}。

## 2、PMT数组 ##

PMT数组是一个被称为部分匹配表的数组，PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度，如：对于字符串”ababa”，它的前缀集合为\{”a”, ”ab”, ”aba”, ”abab”\}，它的后缀集合为\{”baba”, ”aba”, ”ba”, ”a”\}， 两个集合的交集为\{”a”, ”aba”\}，其中最长的元素为”aba”，长度为3。

PMT数组的首位通常设置为0，求PMT数组的时候，对于模式串的位置j，考察patten\[j\]，查找字符串patten\[j\]的最大相等的前缀和后缀，假设最大相等前缀和后缀长度为k，则有k使得  p\[0\]p\[1\]p\[2\]......p\[k-2\]p\[k-1\] = p\[j-k+1\]......p\[j-1\]p\[j\]。

生成PMT数组的程序：

//生成PMT
    void makePMT(const char p[], int pmt[])
    {
    	int q, k;//q:模版字符串下标；k:最大前后缀长度
    	int m = strlen(p);//模版字符串长度
    	pmt[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
    	for (q = 1, k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的pmt值
    	{
    		while (k > 0 && p[q] != p[k]) // 递归的求出P[0]···P[q]的最大的相同的前后缀长度k
    			k = pmt[k-1];
    		if (p[q] == p[k])//如果相等，那么最大相同前后缀长度加1
    		{
    			k++;
    		}
    		pmt[q] = k;
    	}
    }

##   ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70][] ##

##        为了编程的方便， 通常不直接使用PMT数组，而是将PMT数组向后偏移一位，新得到的这个数组称为next数组。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70 1][]

## 3、Next数组 ##

Next数组的首位通常设置为-1，求next数组的时候，对于模式串的位置j，考察patten\[j-1\]，查找字符串patten\[j-1\]的最大相等的前缀和后缀，假设最大相等前缀和后缀长度为k，则有k使得  p\[0\]p\[1\]p\[2\]......p\[k-2\]p\[k-1\] = p\[j-k\]p\[j-k+1\]......p\[j-2\]p\[j-1\]。

生成Next数组的程序：

//生成Next
    void makeNext(const char p[], int next[])
    {
    	next[0] = -1;
    	int i = 0, j = -1;
    	int m = strlen(p);
    	while (i < m)
    	{
    		if (j == -1 || p[i] == p[j])
    		{
    			++i;
    			++j;
    			next[i] = j;
    
    		}
    		else
    			j = next[j];
    	}
    }

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70 2][] ##

## 4、KMP匹配算法 ##

KMP模式匹配算法其实就是利用部分已经匹配的有效信息，保持主串坐标不回溯，通过修改模式串的坐标，是模式串尽量移动到有效位置。KMP模式匹配算法的关键就在于Next数组。

KMP模式匹配算法的代码实现：

int KMP(const char t[], const char p[], int next[])
    {
    	int i = 0, j = 0;
    	int m = strlen(p), n = strlen(t);
    	while (i < n)
    	{
    		if (j == -1 || t[i] == p[j]) 当j为-1时，要移动的是i，当然j也要归0
    		{
    			++i; ++j;
    		}
    		else
    			j = next[j];
    		if (j == m) {
    			return i - m;
    			break;
    		}
    	}
    	return -1;
    }

## 5、KMP算法改进 ##

KMP模式匹配算法改进的重点在于对Next数组的改进，即生成Nextval数组。

从Next数组得到Nextval数组，对于模式串的位置i，若next\[i+1\]=next\[i\]+1，则nextval\[i\]=nextval\[next\[i\]\]，0<=i<=strlen(p)-1；否则nextval\[i\] = next\[i\]。改进过的KMP算法，它是在计算next值的同时，如果a位字符与它的next值执行的b位字符相等，则该a位的nextval值等于b位的nextval值，如果不等，该a位的nextval值就是它自己a位的next值。

生成Next\_val数组代码：

void makeNextval(const char p[],int next_val[])
    {
    
    	next_val[0] = -1;
    	int i = 0, j = -1;
    	int m = strlen(p);
    	while (i < m)
    	{
    		if (j ==-1 || p[i] == p[j])
    		{
    			++i;
    			++j;
    			next_val[i] = (p[i] != p[j] ? j : next_val[j]);
    		}
    		else
    			j = next_val[j];
    
    	}
    }

## 6、BM模式匹配算法 ##

[https://www.cnblogs.com/wxgblogs/p/5701101.html][https_www.cnblogs.com_wxgblogs_p_5701101.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70]: /images/20220311/fe63d1f3328d44d1a23cb49bec708965.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70 1]: /images/20220311/56f01f9389d44fb9ac51e0846afef330.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70 2]: /images/20220311/32013eca0edf45319dab4da108e39cb0.png
[https_www.cnblogs.com_wxgblogs_p_5701101.html]: https://www.cnblogs.com/wxgblogs/p/5701101.html