kmp算法C++-创新互联

文章目录
    • KMP字符串匹配
    • 前缀后缀大值
    • next数组含义
    • KMP匹配算法
    • 如何求next数组
    • 完整代码展示

为平南等地区用户提供了全套网页设计制作服务,及平南网站建设行业解决方案。主营业务为网站设计制作、成都网站制作、平南网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!KMP字符串匹配

一个字符串的子串指的是字符串某一段连续的部分,可以是其本身,判断一个字符串是否是另一个字符串的子串,可以使用 k m p kmp kmp 算法快速匹配上,假设两个子串的长度为 m 、 n m、n m、n,则暴力求解的时间复杂度为 O ( m n ) O(mn) O(mn),而 k m p kmp kmp 的时间复杂度为 O ( m + n ) O(m+n) O(m+n)。

前缀后缀大值

一个长度为N的字符串 S S S,它有 N + 1 N+1 N+1 个前缀(包括空前缀),有 N + 1 N+1 N+1 个后缀

例如:字符串 A B C ABC ABC 有空、 A A A、 A B AB AB、 A B C ABC ABC 四个前缀,有空、 C C C、 B C BC BC、 A B C ABC ABC 四个后缀

前缀后缀大值:对一个长度为 N N N 的字符串 S S S ,找出它的 N + 1 N+1 N+1 个后缀和前缀,按照长度划分,得到 N + 1 N+1 N+1 个对序偶<前缀、后缀>,删除前缀后缀等于字符串本身S的所有<前缀、后缀>中,前缀=后缀且长度大的<前缀、后缀>的长度就是前缀后缀大值。

例如:对于 S = A B A B A B A S=ABABABA S=ABABABA ,按照长度列出前缀、后缀,发现前缀后缀相等的最长前缀后缀为 A B A B A ABABA ABABA ,即前缀后缀大值为 5 5 5 。

前缀后缀相等
yes
AAyes
ABBAno
ABAABAyes
ABABBABAno
ABABAABABAyes
ABABABBABABAno
ABABABABAABABABABAyes(除去本身)
next数组含义

n e x t [ i ] next[i] next[i] 表示 S [ 0... i − 1 ] S[0...i-1] S[0...i−1] 这个前缀的前缀后缀大值,注意这个不是 S [ 0... i ] S[0...i] S[0...i],准确理解 n e x t next next 的含义对理解 k m p kmp kmp 算法很重要。

例如,我们来求 S = A A A B A A A D S=AAABAAAD S=AAABAAAD 的 n e x t next next 数组,我们定义 n e x t [ 0 ] = − 1 next[0]=-1 next[0]=−1。

第一个前缀为 A A A,删除自己本身的前缀后缀是空字符串,所以前缀后缀大值为 0 0 0, n e x t [ 1 ] = 0 next[1]=0 next[1]=0 。

第二个前缀为 A A AA AA,除去自己的前缀有空、 A A A,除去自己的后缀有空、 A A A,大前缀后缀为 A A A, n e x t [ 2 ] = 1 next[2]=1 next[2]=1。

第三个前缀为 A A A AAA AAA,前缀有空、 A A A、 A A AA AA,后缀有空、 A A A、 A A AA AA,大前缀后缀为 A A AA AA, n e x t [ 3 ] = 2 next[3]=2 next[3]=2。

第四个前缀为 A A A B AAAB AAAB,前缀有空、 A A A、 A A AA AA、 A A A AAA AAA,后缀有空、 B B B、 A B AB AB、 A A B AAB AAB,大前缀后缀为空, n e x t [ 4 ] = 0 next[4]=0 next[4]=0。

我们依照上面的流程可以算出来最后的 n e x t next next 数组如下

i012345678
SAAABAAAD
next-101201230
KMP匹配算法

假设我们有两个字符串, S 1 = A A A B A A A B A A A B A A A D S1=AAABAAABAAABAAAD S1=AAABAAABAAABAAAD, S 2 = A A A B A A A D S2=AAABAAAD S2=AAABAAAD,通过一个例子来初步了解以下 K M P KMP KMP算法流程。

首先我们先计算出来 S 2 S2 S2 的 n e x t next next 数组,我们将指针 t 1 t1 t1 指向 S 1 S1 S1 的第零个位置,指针 t 2 t2 t2 指向 S 2 S2 S2 的第零个位置,然后依次往后面匹配,如果 S 1 [ t 1 ] = = S 2 [ t 2 ] S1[t1]==S2[t2] S1[t1]==S2[t2],则 t 1 + + , t 2 + + t1++,t2++ t1++,t2++,如下图所示,匹配到 t 1 = t 2 = 7 t1=t2=7 t1=t2=7 的时候失配了, S 1 [ 7 ] ≠ S 2 [ 7 ] S1[7]\ne S2[7] S1[7]​=S2[7]。
在这里插入图片描述
对于暴力匹配算法,接下来应该是令 t 2 = 0 , t 1 = 1 t2=0,t1=1 t2=0,t1=1,而 k m p kmp kmp 算法不是这样,因为 n e x t next next 数组实际上存放了待匹配字符 S 2 S2 S2 的一些固定特征,可以跳过去一些重复的比较。

接下来,我们查询 7 7 7 号位置的 n e x t next next 值, n e x t [ 7 ] = 3 next[7]=3 next[7]=3,然后令 t 2 = n e x t [ t 2 ] = n e x t [ 7 ] = 3 t2=next[t2]=next[7]=3 t2=next[t2]=next[7]=3,相当于 S 2 S2 S2 往右移动了 ∣ S 2 ∣ − n e x t [ 7 ] |S2|-next[7] ∣S2∣−next[7] ,而 t 1 t1 t1 不变。
在这里插入图片描述
此时 t 1 = 7 , t 2 = 3 t1=7,t2=3 t1=7,t2=3,可以发现 S 1 [ 4..6 ] S1[4..6] S1[4..6] 和 S 2 [ 0..2 ] S2[0..2] S2[0..2] 已经匹配上了,从 t 1 t1 t1 往下继续匹配即可,因为 S 2 S2 S2 的前 3 3 3 个字符和后 3 3 3 个字符相同,换句话说,我们在 S 1 [ 7 ] S1[7] S1[7] 和 S 2 [ 7 ] S2[7] S2[7] 处失配。只需要改变 t 2 t2 t2,我们查询 n e x t [ 7 ] next[7] next[7],即 S 2 [ 0..6 ] S2[0..6] S2[0..6] 的前缀后缀大值,表示这一段前缀等于后缀,且又是长度大的,那么移动后,失配点的前段一定还是匹配的,我们是需要再从失配点 t 1 t1 t1 继续往下匹配即可。

我们继续往后匹配,到了 t 1 = 11 , t 2 = 7 t1=11,t2=7 t1=11,t2=7 时又出现了失配,还是同样的步骤,令 t 2 = n e x t [ t 2 ] = n e x t [ 7 ] = 4 t2=next[t2]=next[7]=4 t2=next[t2]=next[7]=4。
在这里插入图片描述
S 1 S1 S1 未动, S 2 S2 S2 整体向右移动了 ∣ S 2 ∣ − n e x t [ 7 ] |S2| -next[7] ∣S2∣−next[7] 个格子。继续往下匹配,都能匹配成功,说明 S 2 S2 S2 是 S 1 S1 S1 的子串。
在这里插入图片描述
下面是 k m p kmp kmp 算法的代码,如果 j = = − 1 j==-1 j==−1 或者 s 1 [ i ] = = k e y [ j ] s1[i]==key[j] s1[i]==key[j] , i i i 和 j j j 都要增一,否则 i i i 不变, j = n e x t [ j ] j=next[j] j=next[j]。

bool kmp(string s1, string key){int i = 0, j = 0;
	int l1 = s1.size(), l2 = key.size();
	while((i< l1) && (j< l2)){if(j == -1 || s1[i] == key[j]){	i++;
			j++;
		}
		else{j = next_arr[j];
		}
	}
	if(j >= l2)	return true;
	else		return false;
}
如何求next数组

下面举一个例子来说明如何求 n e x t next next 数组,我们要求 n e x t [ k + 1 ] next[k+1] next[k+1],其中 k + 1 = 17 k+1=17 k+1=17,已知 n e x t [ 16 ] = 8 next[16]=8 next[16]=8,则红色框内的元素是一样的,我们只需要判断 p [ 8 ] p[8] p[8] 是否等于 p [ 16 ] p[16] p[16],如果相等,则 n e x t [ k + 1 ] = 8 + 1 = 9 next[k+1]=8+1=9 next[k+1]=8+1=9。
在这里插入图片描述
如果不相等,则看下图,假设 n e x t [ 8 ] = 4 next[8]=4 next[8]=4,则蓝色框内的部分相同。
在这里插入图片描述
由于红色框内是对称的,所以可以得到下图中这四个蓝色框的部分相同,最左边的蓝色框和最右边蓝色框是重合的。
在这里插入图片描述
在这里插入图片描述
如果 p [ 4 ] = = p [ 16 ] p[4]==p[16] p[4]==p[16],则 n e x t [ k + 1 ] = 4 + 1 = 5 next[k+1]=4+1=5 next[k+1]=4+1=5,否则,继续看 n e x t [ 4 ] next[4] next[4],依此类推,直到下标变成了 0 0 0, n e x t [ 0 ] = − 1 next[0]=-1 next[0]=−1。

下面是求 n e x t next next 数组的代码,真正要想理解就自己手动调试一遍,看看是如何求出 n e x t next next 数组的。

void getNext(string p, int *next){int j,k;
	next[0] = -1;
	j = 0;		//后串起始位置,一直增加 
	k = -1;		//k==-1时,令next[1]=0,进入下一轮计算
	while(j< p.size()){if(k==-1 || p[j] == p[k]){	++j;
			++k;
			next[j] = k;
		}
		else
			k = next[k]; 
	}
}
完整代码展示
#include#includeusing namespace std;

int *next_arr;

void getNext(string p, int *next){int j,k;
	next[0] = -1;
	j = 0;		//后串起始位置,一直增加 
	k = -1;		//k==-1时,令next[1]=0,进入下一轮计算
	while(j< p.size()){if(k==-1 || p[j] == p[k]){	++j;
			++k;
			next[j] = k;
		}
		else
			k = next[k]; 
	}
}

bool kmp(string s1, string key){int i = 0, j = 0;
	int l1 = s1.size(), l2 = key.size();
	while((i< l1) && (j< l2)){if(j == -1 || s1[i] == key[j]){	i++;
			j++;
		}
		else{	j = next_arr[j];
		}
	}
	if(j >= l2)	return true;
	else		return false;
}

int main(void){string s1 = "aaabaaabaaabaaad";
	string s2 = "aaabaaad";
	next_arr = (int*) malloc (s2.size()*4);
	getNext(s2, next_arr);
	cout<

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文标题:kmp算法C++-创新互联
网站路径:http://myzitong.com/article/pgcih.html