字符串匹配:Z算法

字符串匹配:Z算法

参考
https://www.cnblogs.com/ycx-akioi/p/Z-algorithm.html
https://www.cnblogs.com/micrari/p/5585984.html

字符串匹配当中算法很多,对于不同的特征的字符串不同的算法表现也有差异,比如对于字符串中出现的字符种类很少而字串很长(如01序列)的时候,KMP算法表现比较好。这儿介绍的Z算法也是一种与KMP类似的一种字符串匹配算法,Z算法当中有个状态数组,叫作Z-数组,是我们需要计算的关键。

对于字符串S,我们有Z-数组z[],其中z-数组中第i位的数值表示从第i位开始与字符串S的开头能完全匹配的长度。z[0]=strlen(S)是显然的,因为从第1位开始与字符串S匹配,整个串S都能完成匹配。以atbadcatbag为例,Z-数组z[]为{11,0,0,1,0,0,4,0,0,1,0}

对于Z-数组,我们将维护一个区间[lwbd,upbd],对于lwbd>1的z[lwbd]若不为0,则upbd=lwbd+z[lwbd]-1 .这个区间[lwbd,upbd]所表示的子串就是与原字符串的头部匹配的子串。

Z数组可以对每一位分别与头部比较,但时间为O(|S|2)。可以采取一种方法仅用O(|S|)的时间就可以计算出Z-数组。

用类似递推的方法,假定已经知道了z[2,…,i-1]与upbd值最大的区间[lwbd,upbd],要计算z[i]并且更新[lwbd,upbd]

[1]如果upbd<i,表示之前匹配过的长子串与当前第i位没有关联,就从第i位开始做枚举求z[i]。若z[i]不为0,则lwbd=i, upbd=lwbd+z[i]-1
[2]否则,记i’=i-lwbd+1,是区间[lwbd,upbd]跨过i平移到后边i的位置。此时会出现两种情况:
[2.1]若i+z[i’]<= upbd,则[i,i+z[i’]]是[lwbd,upbd]的一个真子区间。这样的话,从第i位与a的前缀匹配情况和从第i’位一样,所以z[i]=z[i’],lwbd与upbd不变
[2.2]而i+z[i’]>upbd的情况,i到upbd位的匹配与到upbd-lwbd+1位的匹配一样,即z[i]至少为upbd-i+1,就在此基础之上,从upbd+1位开始匹配,完成后lwbd=i,upbd=i+z[i]-1(此时z[i]必然不为0,这样写是可行的)

void genZBox(char *s)
{
	int z[N],lwbd,upbd,len,i,ii;
	memset(z,0,sizeof(z));
	
	lwbd=0;
	upbd=0;
	len=strlen(s);
	z[0]=len;
	for(i=1;s[i];i++)
	{
		if(upbd<i)
		{
			z[i]=0;
			while( i+z[i]<len && s[i+z[i]]==s[z[i]])
				z[i]++;
			if(z[i]>0)
			{
				lwbd=i;
				upbd=i+z[i]-1;
			}
		}
		else
		{
			ii=i-lwbd+1;
			if(ii<=upbd)
				z[i]=z[ii];
			else
			{
				z[i]=upbd-i+1;
				while(i+z[i]<len && s[i+z[i]]== s[z[i]])
					z[i]++;
				lwbd=i;
				upbd=i+z[i]-1;
			}
		}
	}

	for(i=0;i<len;++i)
	{
		printf("%4d",z[i]);
	}
	printf("\n");

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注