网站运营方案策划技巧-大眼的网站运营知识分享博客

网站运营

网站运营技巧策划方案分享
网站运营知识分享

站长资讯网站运营策划中心

Z算法是一种用于字符串匹配的算法。此算法的核心在于\(z\)数组以及它的求法。

(以下约定字符串下标从\(1\)开始)

\(\bm z\)数组和Z-box

定义\(z\)数组:\(z_{a,i}\)表示从字符串\(a\)的第\(i\)位开始,往后能与\(a\)的前缀匹配的最长长度。显然,\(z_{a,1}=|a|\)恒成立。

一个Z-box是一个区间。给定一个字符串\(a\),那么\(a\)上存在一个Z-box\([l,r]\)当且仅当满足以下全部条件:

\(l\ne1\)

\(z_{a,l}\ne0\)

\(r=l+z_{a,l}-1\)

通俗来说,若从\(a\)的第\(i\)位开始能与\(a\)的前缀匹配至少\(1\)位,那么能匹配的最长的串覆盖过的区间就是一个Z-box。(\(l\ne1\)是因为位置\(1\)很特殊,本身就是前缀,单独考虑)

例如若\(a=``\text{ACACTAAC''}\),那么\(z_{a}=[8,0,2,0,0,1,2,0]\),Z-box有\([3,4],[6,6],[7,8]\)

\(\bm z\)数组的求法

给定字符串\(a\),现在我们需要求出\(z_{a}\)

由于\(z_{a,1}\)的值不用求,而且位置\(1\)比较特殊,就是前缀,所以我们单独处理。

假设我们现在已经知道了\(z_{a,2\sim i-1}\)和使得\(zr\)最大的Z-box\([zl,zr]\),要求出\(z_{a,i}\)并更新\(zl,zr\),那么分\(2\)种情况:

\(zr<i\)。此时我们直接暴力地从第\(i\)位向后匹配求出\(z_{a,i}\)。如果\(z_{a,i}\ne0\),则令\(zl=i,zr=i+z_{a,i}-1\)

\(zr\ge i\)。设\(i-zl+1=i'\),即\(i'\)是把跨越\(i\)的Z-box\([zl,zr]\)平移至\(a\)的前缀处后\(i\)的位置。此时又分\(2\)种情况:

\(i+z_{a,i'}\le zr\)。显然\([i,i+z_{a,i'}]\subsetneq[zl,zr]\)。根据Z-box的定义,\(\forall j\in[i,i+z_{a,i'}],a_j=a_{j-zl+1}\)。那么从\(a\)的第\(i\)位开始与\(a\)的前缀匹配的情况和从第\(i'\)位开始是一样的,直接令\(z_{a,i}=z_{a,i'}\)\(zl,zr\)不变;

\(i+z_{a,i'}>zr\)。同理,\(\forall j\in[i,zr],a_j=a_{j-zl+1}\)。那么\(a\)的第\(i\sim zr\)位与\(a\)的前缀匹配的情况和第\(i'\sim zr-zl+1\)位是一样的,显然\(z_{a,i}\)至少有\(zr-i+1\)这么多,于是直接从第\(zr+1\)位开始暴力向后匹配求出\(z_{a,i}\),并令\(zl=i,zr=i+z_{a,i}-1\)(因为\(z_{a,i}\)不可能为\(0\))。

这样先令\(z_1=|a|\),然后按上述方法从\(i=2\)递推到\(i=|a|\),便可求出\(z_a\)数组。

下面是求\(z\)数组的代码:

//|a|=n void z_init(){//求z数组 z[1]=n;//特殊处理z[1] int zl=0,zr=0;//右端点最大的Z-box for(int i=2;i<=n;i++)//从i=1递推到i=n if(zr<i){//第1种情况 z[i]=0; while(i+z[i]<=s&&a[i+z[i]]==a[1+z[i]])z[i]++;//直接向后暴力匹配 if(z[i])zl=i,zr=i+z[i]-1;//更新右端点最大的Z-box } else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];//第2种情况的第1种情况 else{//第2种情况的第1种情况 z[i]=zr-i+1;//z[i]至少有zr-i+1这么多 while(i+z[i]<=s&&a[i+z[i]]==a[1+z[i]])z[i]++;//后面再暴力匹配 zl=i;zr=i+z[i]-1;//更新右端点最大的Z-box } } 时间复杂度

按上述方法求\(z\)数组的时间复杂度是线性的\(\mathrm{O}(n)\)

证明(感性):观察上述方法可发现,只有当\(i>zr\)时,才可能将这个位置的字符与前缀匹配,而匹配结束后会把\(zr\)更新至最后一个匹配成功的位置,所以每个字符最多会和前缀成功匹配\(1\)次,所以匹配成功的总次数为\(\mathrm{O}(n)\);算\(z_i\)时,如果往后暴力匹配(即遇到的不是第\(2\)种情况的第\(1\)种情况),那么第\(1\)次匹配失败就会停下来,所以匹配失败的总次数也为\(\mathrm{O}(n)\)。因此总时间就是匹配所花的时间\(\mathrm{O}(n+n)=\mathrm O(n)\)再加上一些赋值、更新\(zl,zr\)等一些\(1\)次只要\(\mathrm O(1)\)的操作,就还是\(\mathrm O(n)\)了。

Z算法的应用
首页   建站经验   网站运营策划   网站运营方案   网站运营技巧   关于本站   地图