KMP&Z函数详解

技术分享 4年前 (2022-09-19) 0 999+

关注

KMP

一些简单的定义：

真前缀：不是整个字符串的前缀
真后缀：不是整个字符串的后缀

当然不可能这么简单的，来个重要的定义

前缀函数：
给定一个长度为(n)的字符串(s)，其 (前缀函数) 为一个长度为(n)的数组(pi),其中(pi_i)表示
1. 如果字串(s[0...i])存在一对相等的真前缀和真后缀(s[0...k]~and~s[i-(k-1)...i])，则(pi_i)为这个真前缀（真后缀）的长度(k)
2. 如果有不止一对，则(pi_i)为其中最长的一对
3. 若没有最长的，则(pi_i=0)

简而言之，(pi_i)为字串(s[0...i])最长相等的真前缀和真后缀长度

特别的，规定(pi_0)=0

举个例子，对于字符串(s=)"(abcabcd)",其前缀函数(pi={0,0,0,1,2,3,0})

考虑如何去求前缀函数，最暴力的做法肯定使(O(n^3))的，枚举前缀位置、真前缀（真后缀）的长度和真前缀（真后缀）的每一位，代码就不放出来了（其实是没写）

优化一

我们发现当(i+1)时，(pi_i)最多(+1)，也就是说我们枚举(pi_i)的长度时，上界为(pi{i-1}+1)，这样复杂度可以被优化为(O(n^2))

代码如下

void Getnex(string str){     int len=str.size();     nex[0]=0;     for (int i=1;i<n;i++) {         for (int j=nex[i-1];j>=0;j--) {             if (str.substr(0,j)==str.substr(i-j+1,j)) {                 nex[i]=j;                 break;             }         }     } }

如何证明这个复杂度呢

我们发现每次进行一次(substr)操作，都意味着(pi_i)的值都会(-1)

显然有一种最坏的情况是，(p_i)的值先变成(n-1)，然后再掉回(0)

容易看出这不会超过(O(n))次，然后每次(substr)的复杂度为(O(n))

所以总复杂度(O(n^2))

优化二

我们在优化一中发现了一个性质，当(s[i+1]==s[pi_i])时，(pi_i=pi_{i-1}+1)

考虑把这个性质推下去，当(s[i+1]!=s[pi_i])时

我们发现，我们要找的转移点(j)是要满足(i-1)的前缀性质的

即满足(s[1...j]=s[i-(j-1)...i])

当(pi_i)不行时我们自然要去找下一个满足性质的转移点

很容易想到这东西不就是(pi_{pi_i}吗)

由于真前缀和真后缀相等，所以(pi_{pi_i})必然满足既是真前缀的真前缀又是真后缀的真后缀

可能有点绕，举个例子(s=)"(abaabaa)"（下标从(0)开始）

当我们求(pi_6)时，前面的(pi)值为

(pi[0...5]={0,0,1,1,2,3})

我们发现(s[6]!=s[pi_5=3])

那么我们就需要找到下一个转移点(j)满足(s[0...j]=s[5-(j+1)...5])

因为(pi_5=3)所以(s[0...5])的满足前缀性质的真前缀（真后缀）为(aba)

所以对于字符串"(aba)"满足前缀性质的真前缀（真后缀）一定满足(s[0...5])的前缀性质

所以转移点即为(pi_3=pi_{pi_5})

至此，求前缀函数便可以优化成(O(n))了

void Getnex(std::string S) {     for (int i=2,j=0;i<S.size();i++) {         while(j && S[j+1]!=S[i]) j=nex[j];         if (S[j+1]==S[i]) j++;         nex[i]=j;        } }

前话到此完结，接下来是真正的(KMP)

(KMP)是对于前缀函数的典型运用

举个例子，给定一个文本(t)和字符串(s)，我们尝试求出(s)在(t)中的所有出现

我们记(n,m)为(s)和(t)的长度

我们构造一个字符串为(s+)'(.)'(+t)，其中(.)为不在(s,t)中出现的分隔符

计算出这个字符串的前缀函数，考虑这个前缀函数除去前(n+1)个值意味着什么

根据定义，(pi_i)为右端点为(i)，且为一个前缀的最长真子串长度

且由于有分割符的存在，(pi)不可能超过(n)

当(pi_i=n)时，则意味着(s)在(t)中完整出现一次，其右端点为(i)

因此(KMP)可以在(O(n+m))的复杂度内解决问题

void KMP(std::string S,std::string T) {     for (int i=1,j=0;i<S.size();i++) {         while(j && T[j+1]!=S[i]) j=nex[j];         if (T[j+1]==S[i]) j++;         if (j==m-1) {             std::cout<<i-m+2<<std::endl;             j=nex[j];         }     } }

字符串的周期

定义：

对于字符串(s)，若存在(p)满足(s[i]=s[i+p](iin[0,|s|-p-1]))，则(p)为(s)的周期
对于字符串(s)，若存在(r)满足(s)长度为(r)的前缀和长度为(r)的后缀相等，则称(s)长度为(r)的前缀是(s)的(border)

由这两个定义不难看出(|s|-r)是(s)的周期

根据前缀函数的定义我们可以得出(s)所有(border)长度，即(pi_{n-1},pi_{pi_{n-1}},...)

所以我们可以在(O(n))的时间复杂度内求出(s)的所有周期

其中最小周期为(n-pi_{n-1})

统计每个前缀的出现次数

以下默认字符串下标从(1)开始

主要是两种问题，一个是求(s)的前缀在(s)中的出现次数，另一个是求(s)的前缀在另一个字符串(t)中的出现次数

考虑位置(i)的前缀函数值(pi_i)，根据定义，其意味着字符串(s)一个长度为的前缀在位置(i)出现并以(i)为右端点，同时不存在一个更长的前缀满足前述定义。

与此同时，更短的前缀可能以该位置为右端点。

容易看出，我们遇到了在计算前缀函数时已经回答过的问题：给定一个长度为(j)的前缀，同时其也是一个右端点位于(i)的后缀，下一个更小的前缀长度(k<j)是多少？该长度的前缀需同时也是一个右端点为(i)的后缀。

因此以位置(i)为右端点，有长度为(pi_i)的前缀，有长度为(pi_{pi_i})的前缀，等等，直到长度变为0。

故而我们可以通过下述方式计算答案。

void Getcnt(std::string str) {     for (int i=1;i<str.size();i++) ans[nex[i]]++;     for (int i=str.size()-1;i>0;i--) ans[nex[i]]+=ans[nex[i]];     for (int i=1;i<str.size();i++) ans[i]++; }

例题：CF432D Prefixes and Suffixes

题意：

给你一个长度为n的长字符串，“完美子串”既是它的前缀也是它的后缀，求“完美子串”的个数且统计这些子串的在长字符串中出现的次数

模板题，直接写就行

#include <ctime> #include <cstdio> #include <iostream> #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)  const int maxn=1e5+5; int n,nex[maxn],ans[maxn]; std::string str;  void chkmax(int &x,int y) {if (x<y) x=y;} void chkmin(int &x,int y) {if (x>y) x=y;} int read() {     int x=0,f=1;     char ch=getchar();     while(ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}     while(ch<='9' && ch>='0') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}     return x*f; }  void Getnex(std::string s) {     for (int i=2,j=0;i<s.size();i++) {         while(j && s[j+1]!=s[i]) j=nex[j];         if (s[j+1]==s[i]) j++;         nex[i]=j;     } } void out(int i,int cnt) {     if (!i) {std::cout<<cnt<<std::endl;return ;}     out(nex[i],cnt+1);     std::cout<<i<<' '<<ans[i]<<std::endl; }  int main() {     std::cin>>str;     str=" "+str;     Getnex(str);     // for (int i=1;i<str.size();i++) std::cout<<nex[i]<<' ';puts("");     for (int i=1;i<str.size();i++) ans[nex[i]]++;     for (int i=str.size();i>=1;i--) ans[nex[i]]+=ans[i];     for (int i=1;i<str.size();i++) ans[i]++;     out(str.size()-1,0);     return 0; }

Z函数（扩展KMP）

定义:

对于一个字符串(s)，(z[i])表示(s)和(s[i...n-1])的(LCP)(最长公共前缀)的长度，(z)则被称为(s)的(Z)函数

我们在计算的时候，可以通过前面已知的(z)来计算

对于(i)，我们称区间([i,i+z[i]-1])为(i)的匹配段

我们在算法过程中维护右端点最靠右的匹配段，记作([l,r])

则有([l,r])为(s)的前缀，并且在计算(z[i])时我们保证(lleq i)

算法流程

最开始时，(l=r=0)

在计算(z[i])的过程中

若(ileq r)，则有(s[i,r]=s[i-l,r-l])，所以(z[i]ge min(z[i-l,r-i+1]))
- 若(z[i-l]<r-i+1)，则(z[i]=z[i-l])
- 若(z[i-l]ge r-i+1)，我们令(z[i]=r-i+1)，然后暴力向后枚举字符
若(i>r)，我们直接暴力从(s[i])开始比较，求出(z[i])
求出(z[i])后，还要更新(l,r)

void GetZ(std::string s) {     int l=0,r=0;     for (int i=1;i<s.size();i++) {         if (i<=r && z[i-l]<r-i+1) z[i]=z[i-l];         else {             z[i]=std::max(0,r-i+1);             while(i+z[i]<s.size() && s[z[i]]==s[i+z[i]]) z[i]++;         }         if (i+z[i]-1>r) {l=i;r=i+z[i]-1};     } }