Z函数+扩展KMP

# Z函数及扩展KMP

## 1.0 Z函数定义及示例

首先Z函数是啥? 其定义为Z(i):

为s和s[i, n]的最长公共前缀(LCP)(这里假定字符序列都是从下标1开始，下文就不赘述)。

用更加形式一点的描述就是:

Z(i) = max{x | s[1, x] = s[i, i + x -1]},特别地

Z(1) = 0;这里和KMP一样不考虑平凡串形式(即)。

当然也有的人将z(1) = n, 不管如何都是在这一点需要进行特殊的初始化。

这里以https://zhuanlan.zhihu.com/p/403256847

提供的示例进行分析:

对于字符串s = "aabcaabcaaaab",其Z函数表

那么怎么快速求出这张表呢?

最直接也是最暴力的做法就是枚举，每个起始索引，然后去遍历s[i, i + x -1] = [1, x], 当上面成立时，则z[i]++。这样为了得到这张表，我们需要O(n^2)的时间复杂度，类似于KMP算法，为了求得next数组，最开始也是暴力做法，但是通过next数组可以在O(n)时间复杂度内完成匹配。

//https://oi-wiki.org/string/z-func/
// C++ Version
vector z_function_trivial(string s) {
  int n = (int)s.length();
  vector z(n);
  for (int i = 1; i < n; ++i)
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
  return z;
}

这里Z函数就是类型我们的next数组的形式，下面让我们来看一看。为了解决这个问题，需要引入一个定义Z-Box:

当Z(i) != 0时， 定义区间[i, i + z(i) -1]就是一个Z-Box。

根据定义， Z-Box就是字符串s的一个区间[l, r] = [i, i + z(i) -1]满足s[l, r]是s的前缀(不一定要求最长， 会随着i的移动而变化)。在位置i时， [l, r]必须包含位置i，且使得r尽可能大(即尽可能靠右)。

对于s = "bacbcbacba"

对于s[4] = b, 其该位置z(4) = 1, 所以其Z-Box = [4, 4], 窗口大小为1。

对于s[6] =b, 其位置z(6) = 4, 因为此处Z-Box为[6, 9], 窗口大小为4。

对于s[8] = c, 其位置的z(0) = 0, 根据上面的描述，这时不可用[i, i + z(i) - 1]这个定义了，那么可以利用另一个[l, r]区间覆盖定义，那么区间[5, 9]可以覆盖s[8],并且满足前缀要求，且r的位置尽可能大，因此其Z-Box为[5, 9]。

对于s[10]= b, 其z(i) = 2, 因此Z-Box直接为[10, 11]。

通过上面我们理解了Z-Box，下面我们借助Z-Box来求解Z()函数。

当在i-1位置处我们知道了Z-Box， 现在需要求解z(i)和在i位置处的Z-Box。

现在知道i-1处的Z-Box为[l, r], 那么由其定义可以得到s[l, r] = s[1, r - l + 1], 那么i处位置对应的是i - l + 1处位置的字符串。

1）当z(i -l +1) < r - i + 1时，那么s[i-l + 1, i - l + 1 + z(i - l +1) -1] = s[1, z(i - l +1)] = s[i, i + z(i) - 1], 因此z(i) = z(i - l +1), 又因为i + z(i) - 1依旧处于Z-Box[l, r]中，所以此时不需要对Z-Box进行更新。

2）当z(i - l +1) >= r -i + 1时，s[i - l +1, r -l + 1] = s[i, r], 其前缀长度相等，但是在Z-Box侧外的位置则无法判定，所以从这个位置开始，通过枚举来确定

z(i),并且更新Z-Box；

z[i] = r - i + 1;
while(s[i + z[i]] == s[1 + z[i]])
    z[i]++;
l = i, r = i + z[i] - 1; //更新Z-Box范围

3）上面我们讨论的都是i处于i-1的Z-Box范围内，当i一开始就处于Z-Box右侧，这时由于不清楚具体状况，只能通过枚举来计算z[i]。

这里思考一下，为什么Z-Box要求r尽可能靠右?

A:这样可以使得更多的数能落到1)中进行计算，这时计算就是O(1)。

不然其他情况会部分退化或者完全退化暴力枚举情况。

因为求z(i)需要从1~n, 时间复杂度为O(n).

Z-Box右端点最多右移n次，O(n).所以时间复杂为O(n)。

将上述思路整理成代码就是:

void get_zFunc(int n, char* s)
{
    //从下标1开始;
    z[1] = 0/ n; //两种情况，初始化，进行特殊处理;
    int l = 0, r = 0; //定义起始Z-Box窗口;
    for (int i = 2; i <= n; i++) {
        if (i > r) { //大于窗口右端点，对应情况3的分析;
            while (i + z[i] <= n && s[i + z[i]] == s[1 + z[i]])
                z[i]++;
            l = i, r = i + z[i] - 1; //更新Z-Box窗口;
        } else if (z[i - l +1] < r - i + 1) { //case 1:
            z[i] = z[i - l + 1]; 
        } else {  //case 2:
            z[i] = r - i + 1;
            while (i + z[i] <= n && s[i + z[i]] = s[1 + z[i]]) 
                z[i]++;
            l = i, r = i + z[i] - 1; //更新Z-Box;
        }
    }
}

扩展KMP算法

主要是在Z函数基础上进行进一步扩展。

问题:给定字符串s1, s2, 求出s1的每一个后缀与s2的最长公共前缀。

借助Z函数我们可以在O(n)时间复杂度范围内完成。

特化:

当s1 == s2, 那么就是求解同一个字符串s1的后缀和前缀的最长串(LCP), 这个时候就对应着上面所讲解的Z函数求解。

更加一般的情况:

当s1 != s2, 适当修改Z函数的定义即可，

定义数组ext_z[i]：s1[i]开始的后缀与s2的最长公共前缀。

同样地，对Z-Box进行扩展为ExtZ-Box:

字符串s1[l, r]，满足s1[l, r]是s2的前缀，且随着i的变化而移动，

在位置i处，[l,r]必须包含i，且r尽可能大。

形式化定义为:

ExtZ-Box：[i, i + ExtZ-Box(i) -1]。

根据类似Z函数计算过程，同样分成3种情况进行分析。

现在变成s1和s2上进行转换。

下面为了简化，还是用z代称ext_z

1）.当z[i -l + 1]

2)当z[i - l + 1] >= r - l + 1, z[i]从r处开始扫描，从而确定z(i), 最后更新Z-Box区间;

3).当i > r时， 从i处开始扫描，从而确定z(i), 最后更新一下Z-Box区间即可。

相关代码实现:

void get_extZfunc(string& s1, string& s2)
{
    int n  = s1.size(), m = s2.size();
    int cur = 0;
    while (cur < n && cur < m && s1[cur] == s2[cur])
        cur++;
    p[0] = cur; 

    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i > r) {
            while (i + p[i] < n && p[i] < m && s1[i + p[i]] == s2[p[i]])
                p[i]++;
            l = i, r = i + p[i] - 1;
        } else if (z[i - l] < r - i + 1) {
            p[i] = z[i - l];
        } else {
            p[i] = r -  i + 1;
            while (i + p[i] < n && p[i] < m && s1[i + p[i]] == s2[p[i]])
                p[i]++;
            l = i, r =i + p[i] - 1;
        }
    }
}

注意和KMP的区间，KMP中next数组用的是以i结尾的子串去匹配前缀，而这里是以i以开始的子串去和前缀匹配。

相关例题

1. Lougu P5410 扩展KMP(Z函数)

   #include 
   using namespace std;
   using LL = long long;
   const int N = 2e7 + 20;
   LL z[N], p[N];
   
   void get_zFunc(std::string& s)
   {
       int l = 0, r = 0;
       int n = s.size();
       z[0] = n;
       for (int i = 1; i < n; i++) {
           if (i > r) {
               while (i + z[i] < n && s[i + z[i]] == s[z[i]])
                   z[i]++;
               l = i, r = i + z[i] - 1;
           } else if (z[i - l] < r - i + 1) {
               z[i] = z[i - l];
           } else {
               z[i] = (r - i + 1);
               while (i + z[i] < n && s[i + z[i]] == s[z[i]]) 
                   z[i]++;
               l = i, r = i + z[i] - 1;
           }
       }
   }
   
   void get_extZfunc(string& s1, string& s2)
   {
       int n  = s1.size(), m = s2.size();
       int cur = 0;
       while (cur < n && cur < m && s1[cur] == s2[cur])
           cur++;
       p[0] = cur;
   
       int l = 0, r = 0;
       for (int i = 1; i < n; i++) {
           if (i > r) {
               while (i + p[i] < n && p[i] < m && s1[i + p[i]] == s2[p[i]])
                   p[i]++;
               l = i, r = i + p[i] - 1;
           } else if (z[i - l] < r - i + 1) {
               p[i] = z[i - l];
           } else {
               p[i] = r -  i + 1;
               while (i + p[i] < n && p[i] < m && s1[i + p[i]] == s2[p[i]])
                   p[i]++;
               l = i, r =i + p[i] - 1;
           }
       }
   }
   
   int main()
   {
       string s1, s2;
       std::ios::sync_with_stdio(false);
       std::cin >> s1 >> s2;
   
       int n = s1.size(), m = s2.size();
       get_zFunc(s2);
       get_extZfunc(s1, s2);
       
       LL res = 0;
       for (int i = 0; i < m; i++) {
           res ^= (i+1)*(z[i]  + 1);
       }
       cout << res << endl;
       res = 0;
       for (int i = 0; i < n; i++)
           res ^= (i+1)*(p[i] + 1);
   
       cout << res << endl;
       return 0;
   }
   

2. leetcode 2223

   class Solution {
   public:
   
       using LL = long long;
   
       void get_zFunc(string& s, vector& z)
       {
           int n = s.size();
           z[0] = n;
           int l = 0, r = 0;
           for (int i = 1; i < n; i++) {
               if (i > r) {
                   while (i + z[i] < n && s[i+z[i]] == s[z[i]])
                       z[i]++;
                   l = i, r = i + z[i] - 1;
               } else if (z[i - l] < r - i + 1) {
                   z[i] = z[i - l];
               } else {
                   z[i] = r - i + 1;
                   while (i + z[i] < n && s[i + z[i]] == s[z[i]])
                       z[i]++;
                   l = i, r = i + z[i] - 1;
               }
           }
       } 
   
       long long sumScores(string s) {
           vector z(s.size(), 0);
           get_zFunc(s, z);
   
           LL res = 0;
           for (auto c : z)
               res += c;
           return res;
       }
   };
   

参考

1.https://www.bilibili.com/video/BV1LK4y1X74N?spm_id_from=333.337.search-card.all.click

2.https://zhuanlan.zhihu.com/p/403256847

3.https://oi-wiki.org/string/z-func/

4.https://www.luogu.com.cn/problem/solution/P5410?page=1