【字符串】 Z-algorithm

时间:2019-09-05
本文章向大家介绍【字符串】 Z-algorithm,主要包括【字符串】 Z-algorithm使用实例、应用技巧、基本知识点总结和需要注意事项,具有一定的参考价值,需要的朋友可以参考一下。

Z-algorithm

Algorithm

Task

给定一个文本串 \(S\) 和一个模式串 \(T\),求 \(T\) 对于 \(S\) 的每个后缀子串的公共前缀子串。

Limitations

要求时空复杂度均为线性

Solution

\(X\) 是一个字符串,则以下表述中,\(X_u\) 代表 \(X\) 的第 \(u\) 个字符,\(X_{u \sim v}\) 代表 \(X\) 的从 \(u\) 起到 \(v\) 结束的字串。

\(n = |S|,~m = |T|\)

考虑按照长度由大到小扫描 \(S\) 的后缀字串,设当前要求 \(S_{i \sim n}\)\(T\) 的公共前缀子串,则 \(\forall k \in [1, ~i),~S_{k \sim n}\) 的答案都已计算完成。

设先前的计算中,匹配到 \(S\) 最远的一次为第 \(p\) 次,即 \(p + ans_p\) 在所有 \(k + ans_k\) 中最大,设 \(q = p + ans_p\)。显然有 \(p < i\)

首先不妨设 \(q \geq i\)\(q < i\) 的情况将在下方说明。

\(j = i - p + 1\),不难发现 \(T_j = S_i\),即 \(j\)\(S_i\) 的对应匹配位置。

由于所求是公共前缀字串,因此有

\[S_{p \sim q} = T_{1 \sim ans_p}\]

引入一组辅助变量,设 \(next_j\)\(T_{j \sim m}\)\(T\) 的最长公共前缀子串长度。

根据定义,有

\[T_{j \sim j + next_j} = T_{1 \sim next_j}\]

分两种情况讨论。

第一种情况,\(j + next_j < q\),即 \(T_{j \sim j + next_j}\)\(S_{p \sim q}\) 的字串,因此有

\[T_{j \sim j + next_j} = S_{i \sim i + next_j}\]

又因为 \(T_{j \sim j + next_j} = T_{1 \sim next_j}\)(已证),等量代换得到

\[S_{i \sim i + next_j} = T_{1 \sim next_j}\]

对于 \(S_i + next_j + 1\),则可以用反证法证明其不等于 \(T_{next_j + 1}\),否则由于 \(T_{j + next_j + 1}\) 依然是 \(S_{p \sim q}\) 的字串,所以 \(T_{j + next_j + 1} = T_{next_j + 1}\),这与 \(next_j\) 是最长前缀公共子串矛盾。

因此,对于这种情况,答案即为 \(next_j\)

第二种情况,\(j + next_j \geq q\),即 \(T_{j \sim j + next_j}\) 不全是是 \(S_{p \sim q}\) 的字串,因此有

首先可以用与第一种情况相同的证明方式证明 \(S_{i \sim q} = T_{1 \sim q - i + 1}\),即 \(q\) 及以前的字符可以与 \(T\) 完美匹配,而对于 \(q\) 后面的字符,我们暴力将其与 \(T\) 匹配,同时更新 \(p\)\(q\) 的位置即可。

对于 \(q < i\) 的情况,显然 \(q = i - 1\),直接继续暴力进行匹配即可。

考虑时间复杂度:

除掉暴力匹配的环节,剩下的部分显然都是单次 \(O(1)\) 完成,因此这一部分的复杂度是线性的。

考虑每次暴力匹配都会让 \(q\) 右移,所以暴力匹配的次数是线性的,而单次暴力匹配是 \(O(1)\) 的,因此算法的时间复杂度是线性的。

考虑 \(next\) 数组的计算:我们发现这相当于令文本串 \(S = T\),只需要预处理 \(next_1\)\(next_2\),可以发现从 \(next_3\) 起,计算所需要的 \(next\) 值都已经在之前被计算过。

Sample

【P5410】 【模板】扩展 KMP

Description

给定一个文本串 \(S\) 和一个模式串 \(T\),求 \(T\) 对于 \(S\) 的每个后缀子串的公共前缀子串。并输出 \(T\) 的每个后缀字串与 \(T\) 的公共前缀子串长度。

Limitations

字符串长度不超过 \(10^5\)

Solution

板板题。算法在实现上比较吃细节,注意比较大于小于的时候是否应该加等于号。记得对拍

Code

#include 
#include 
#include 

const int maxn = 100005;

int nxt[maxn];
char S[maxn], T[maxn];

void Z_algorithm(const char *const A, const char *const B, const int x, const int y, const bool pt);

int main() {
  freopen("1.in", "r", stdin);
  scanf("%s\n%s", S + 1, T + 1);
  int x = strlen(S + 1), y = strlen(T + 1);
  nxt[1] = y;
  Z_algorithm(T, T, y, y, false);
  for (int i = 1; i <= y; ++i) {
    qw(nxt[i], i == y ? '\n' : ' ', true);
  }
  Z_algorithm(S, T, x, y, true);
  putchar('\n');
  return 0;
}


void Z_algorithm(const char *const A, const char *const B, const int x, const int y, const bool pt) {
  int p = 0, q = 1;
  if (!pt) {
    while ((q < x) && (A[q] == A[q + 1])) ++q;
    nxt[p = 2] = q - 1;
    q = std::max(q, 2);
  } else {
    while ((q <= x) && (q <= y) && (A[q] == B[q])) ++q;
    p = 1;
    qw(--q, ' ', true);
  }
  for (int i = pt ? 2 : 3, _ans; i <= x; ++i) {
    int a = i - p + 1;
    int len = nxt[a];
    if ((i + len - 1) >= q) {
      _ans = std::max(0, q - i + 1);
      while ((q < x) && (_ans < y) && (A[q+1] == B[_ans+1])) {
        ++_ans; ++q;
      }
      q = std::max(p = i, q);
    } else {
      _ans = len;
    }
    if (pt) {
      qw(_ans, ' ', true);
    } else {
      nxt[i] = _ans;
    }
  }
}

$flag 上一页 下一页