Z-algorithm字符串匹配 算法小结

时间：2023-01-06 22:08:53

昨天学习了字符串匹配，一种新算法Z-algorithm，现作如下总结。

算法大意

Z-algorithm是用于字符串匹配。定义z[i]表示以i开头的子串和原串的最长公共前缀。我们通过线性时间计算出整个串的z数组，从而进行一些字符串的相关操作，该算法等价于扩展KMP。

如何操作

我们通过已知的串s和z[1]…z[i-1]来求z[i]。
设想一个z数组，z[i]表示他的最长公共前缀即s[i]…s[i+z[i]].我们将其称之为i这个位置控制的范围，称为一个Z-box。我们定义l,r为右端点最靠右的Z-box的控制范围（即i和i+z[i]）。下面进行分类讨论。
1.若i > r，则证明前面的所有Z-box和我们没有任何关联，我们无法利用，同时也证明i这个位置的Z-box一定是最靠右的，更新l=r=i，暴力匹配。
2.若i < r，则令k=i-l，因为i位于Z-box内，则我们知道s[l]…s[r]应该与s[0]..s[r-l]匹配，所以此处的k对应的是i∈[l,r]这个位置在前缀即[0,r-l]中的对应位置，故我们可以根据z[k]的数值来计算我们的z[i]。令z[i]=min(z[k],r-i+1).Z-box在这里会有两种可能。(1)包含。k这个位置控制的Z-box的右端点并没有超过[l,r]这个Z-box的右端点，直接令z[i]=z[k]。(2)超过。k这个位置控制的Z-box的右端点超过了超过了[l,r]对应的前缀。因为我们仅仅知道s[l]…s[r]与s[0]..s[r-l]匹配，后面的部分一概不知，所以我们令l=i，继续暴力匹配后面的长度，匹配完成后令z[i]=r-l即可。

复杂度

复杂度线性。不用太过严格证明，我们说说道理。不难看出r这个指针是单调递增的。证毕。

代码实现

void get_z()
{
    int l=0,r=0;
for (int i=1;i<n;i++)
    {
if (i>r)
        {
            l=i,r=i;
while (r<n && s[r-l]==s[r]) r++;
            z[i]=r-l,r--;
        }
else
        {
            int k=i-l;
if (z[k]<r-i+1) z[i]=z[k];
else
            {
                l=i;
while (r<n && s[r-l]==s[r]) r++;
                z[i]=r-l,r--;
            }
        }
    } 
}

算法应用

几道例题看看这个算法怎么用。

Codeforces 126B Password

链接信手拈来

题目大意：你要在一个串中找到“密码”，密码定义为既是前缀，也是后缀，同时在串中间出现过的子串。

思路：用到了字符串匹配。我们先预处理处z数组。如何保证前缀也是后缀呢?z[i]==n-i.直观理解上就是以这一位为开始的串有n-i位与前缀相同。显而易见这说的就是后缀和前缀相等。那如何保证这一个串在中间也出现过呢？遍历的过程中记录一个z[i]的最大值maxx，若这个maxx>=n-i，则说明前面至少出现过不短于他的一个和前缀相同的串。输出。

代码如下

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
long long f=1,sum=0;
char c=getchar();
while (c<'0' || c>'9')
    {
if (c=='-') f=-1;
        c=getchar();
    }
while (c>='0' && c<='9')
    {
        sum=sum*10+c-'0';
        c=getchar();
    }
return sum*f;
}
const int MAXN=1000010;
char s[MAXN];
int z[MAXN],n;
void get_z()
{
int l=0,r=0;
for (int i=1;i<n;i++)
    {
if (i>r)
        {
            l=i,r=i;
while (r<n && s[r-l]==s[r]) r++;
            z[i]=r-l,r--;
        }
else
        {
int k=i-l;
if (z[k]<r-i+1) z[i]=z[k];
else
            {
                l=i;
while (r<n && s[r-l]==s[r]) r++;
                z[i]=r-l,r--;
            }
        }
    } 
} 
int main()
{
scanf("%s",s);
    n=strlen(s);
    get_z();
int maxx=0,pos=0;
for (int i=1;i<n;i++)
    {
if (z[i]==n-i && maxx>=n-i)
        {
            pos=i;
break;
        }
        maxx=max(maxx,z[i]);
    }
if (!pos) printf("Just a legend");
else for (int i=0;i<n-pos;i++) putchar(s[i]);
return 0;
}

Codeforces 535D Tavas and Malekas

继续拈链接

题目大意：给你一个模式串和原串的长度，并且告诉你模式串再原串中出现的位置，求原串有几种可能。

思路： 计算出模式串的z数组待用。
读进来每一个位置，先判断答案是否可行。有两种可能：这个串和前一个串有重合或没有重合。没有重合我们就默认他可以放在这里。如果有重合怎么办呢？前面的z数组就可以派上用场了。计算出重合的长度吗，如果这段长度的后缀和前缀是完全匹配的，那么就可以，否则就是不合法的。
因为是计算方案数，所以我们需要找出没有被锁死的位置来计算总数，采用差分的方法，区间打上标记表示被占用过，最后加起来看看哪里的标记是0，计算26的乘方即可。

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
long long f=1,sum=0;
char c=getchar();
while (c<'0' || c>'9')
    {
if (c=='-') f=-1;
        c=getchar();
    }
while (c>='0' && c<='9')
    {
        sum=sum*10+c-'0';
        c=getchar();
    }
return sum*f;
}
const int MAXN=1000010;
const int Mod=1e9+7;
char s[MAXN];
int z[MAXN],n,m,pos[MAXN],N;
void get_z()
{
int l=0,r=0;
for (int i=1;i<N;i++)
    {
if (i>r)
        {
            l=i,r=i;
while (r<N && s[r]==s[r-l]) r++;
            z[i]=r-l,r--;
        }
else
        {
int k=i-l;
if (z[k]<r-i+1) z[i]=z[k];
else
            {
                l=i;
while (r<N && s[r]==s[r-l]) r++;
                z[i]=r-l,r--;
            }
        }
    }
}
bool check(int x,int y)
{
if (x+n<=y) return true;
return z[y-x]>=x+N-y;
}
int quickpow(int a,int b)
{
    ll ans=1,x=a;
while (b)
    {
if (b&1) ans*=x;
        b/=2;
        x*=x;
        ans%=Mod,x%=Mod; 
    }
return (int)ans;
}
int a[MAXN];
int main()
{
scanf("%d%d",&n,&m);
if (!m)
    {
printf("%d",quickpow(26,n));
return 0;
    }   
scanf("%s",s);
    N=(int)strlen(s);
    get_z();
for (int i=1;i<=m;i++)
    {
scanf("%d",&pos[i]);
        pos[i]--;
    }
int tot=0;
for (int i=1;i<m;i++)
    {
if (check(pos[i],pos[i+1]))
            a[pos[i]]++,a[pos[i]+N]--;
else 
        {
printf("0");
return 0;
        }
    }
    a[pos[m]]++,a[pos[m]+N]--;
for (int i=0;i<n;i++)
        a[i]+=a[i-1]; 
for (int i=0;i<n;i++)
if (!a[i])
            tot++;
printf("%d",quickpow(26,tot));
return 0;
}

Codeforces 631D Messenger

链接又一次被拈过来了

题目大意：定义一种奇怪的二元组< char , int >，表示前一个字符连续出现了几次，用这种二元组表示出文本串和模式串。问在文本串中能够匹配多少次模式串。

思路：思路也很清奇。最初一看似乎无从下手，但是我们发现，其实这个串想要匹配的条件其实很苛刻。仔细一想，去掉头尾两个二元组的话，中间那些部分必须完全相等才能匹配。我们采用如下方式构造新串：将文本串（大串）接在去掉头尾两个二元组的模式串上，获取它的z数组。
然后我们就可以先找到能够匹配中间部分的位置，此时我们再单独比较头尾是否可行即可。
这种方法需要特判1，因为去掉头尾是无法看出长度为1的串的。。。

代码：

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
long long f=1,sum=0;
char c=getchar();
while (c<'0' || c>'9')
    {
if (c=='-') f=-1;
        c=getchar();
    }
while (c>='0' && c<='9')
    {
        sum=sum*10+c-'0';
        c=getchar();
    }
return sum*f;
}
const int MAXN=200010;
int z[2*MAXN];
ll t1[MAXN],t2[MAXN];
char s1[MAXN],s2[MAXN],s[2*MAXN];
ll t[2*MAXN];
int main()
{
int n,m;
char tmp[5],last='$';
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
    {
int x;
scanf("%d",&t1[i]);
scanf("%s",tmp);
if (tmp[1]==last) i--,n--,t1[i]+=t1[i+1];
        s1[i]=tmp[1];
        last=tmp[1];
    }
    last='$';
for (int i=1;i<=m;i++)
    {
int x;
scanf("%d",&t2[i]);
scanf("%s",tmp);
if (tmp[1]==last) i--,m--,t2[i]+=t2[i+1];
        s2[i]=tmp[1];
        last=tmp[1]; 
    }
if (m==1)
    {
        ll ans=0;
for (int i=1;i<=n;i++)
        {
if (s1[i]!=s2[1]) continue;
if (t1[i]<t2[1]) continue;
            ans+=(t1[i]-t2[1]+1);
        }
cout<<ans;
return 0;
    }
for (int i=2;i<m;i++)
        s[i-2]=s2[i],t[i-2]=t2[i];
for (int i=1;i<=n;i++)
        s[i+m-2]=s1[i],t[i+m-2]=t1[i];
int N=n+m-1;
int l=0,r=0;
for (int i=1;i<N;i++)
    {
if (i>r)
        {
            l=i,r=i;
while (r<N && t[r]==t[r-l] && s[r]==s[r-l]) r++;
            z[i]=r-l,r--;
        }   
else
        {
int k=i-l;
if (z[k]<r-i+1) z[i]=z[k];
else
            {
                l=i;
while (r<N && t[r]==t[r-l] && s[r]==s[r-l]) r++;
                z[i]=r-l,r--;
            }
        }
    }
int ans=0;
for (int i=m-1;i<=m+n-2;i++)
    {
if (z[i]!=m-2) continue;
if (s[i-1]!=s2[1]) continue;
if (s[i-2+m]!=s2[m]) continue;
if (t[i-1]<t2[1]) continue;
if (t[i-2+m]<t2[m]) continue;
        ans++;
    }
cout<<ans;
return 0;
}

Codeforces 149E Martian Strings

链接啊链接

题目大意：给定一个文本串和多个模式串，问有多少个串能被拆分成恰好两段被匹配到。

思路：肯定是一个模式串一个模式串的分开做。对于每一个模式串，我们将文本串接在模式串后面，处理出新串的z数组。
再定义一个新数组pos[i]表示模式串长度为i的前缀最小被匹配到的位置。然后把模式串和文本串分别反过来，再次匹配，匹配到长度为len-i时判断是否合法即可。

代码：

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
long long f=1,sum=0;
char c=getchar();
while (c<'0' || c>'9')
    {
if (c=='-') f=-1;
        c=getchar();
    }
while (c>='0' && c<='9')
    {
        sum=sum*10+c-'0';
        c=getchar();
    }
return sum*f;
}
const int MAXN=200010;
const int MAXM=1010;
char s[MAXN],c[MAXN],S[MAXN];
int z[MAXN],N,pos[MAXM],n,len,tot;
void get_z()
{
int l=0,r=0;
for (int i=1;i<=n+len;i++)
    {
if (i>r)
        {
            l=i,r=i;
while (r<n+len && s[r]==s[r-l]) r++;
            z[i]=r-l,r--;
        }
else 
        {
int k=i-l;
if (z[k]<r-i+1) z[i]=z[k];
else
            {
                l=i;
while (r<n+len && s[r]==s[r-l]) r++;
                z[i]=r-l,r--;
            }
        }
if (i>len && z[i]) pos[z[i]]=min(pos[z[i]],i-len+z[i]-1); 
    }
}
void get_Z()
{
int l=0,r=0;
for (int i=1;i<=n+len;i++)
    {
if (i>r)
        {
            l=i,r=i;
while (r<n+len && S[r]==S[r-l]) r++;
            z[i]=r-l,r--;
        }
else 
        {
int k=i-l;
if (z[k]<r-i+1) z[i]=z[k];
else
            {
                l=i;
while (r<n+len && S[r]==S[r-l]) r++;
                z[i]=r-l,r--;
            }
        }
if (i>len) if (pos[len-z[i]]<=n+len-i-z[i]+1) {tot++;break;}
    }
}
int main()
{
scanf("%s",c);
    n=(int)strlen(c);
int T;
    tot=0;
scanf("%d",&T);
while (T--)
    {
memset(pos,inf,sizeof(pos));
scanf("%s",s);
        len=strlen(s);
if (len<2) continue;
for (int i=0;i<n;i++)
            s[i+len+1]=c[i];
for (int i=0;i<len;i++)
            S[i]=s[len-i-1];
for (int i=0;i<n;i++)
            S[i+len+1]=c[n-i-1];
        S[len]='$',s[len]='$';
        get_z();
for (int i=len-1;i>=1;i--)
            pos[i]=min(pos[i+1]-1,pos[i]);
        get_Z();
    }
cout<<tot;
return 0;
}

该算法的用法

大概就是字符串匹配吧。模式串+’$’+文本串是一个很好的选择。

标签：

相关文章