Z Algorithm

Z Algorithm

Z 算法,也即擴展 KMP。z 函數與 $\pi$ 函數區別在於,$z[i]$ 表示的是以 $i$ 為起始點與前綴匹配的最大長度,而 $\pi[i]$ 則是以 $i$ 為結尾。

z函數的計算方法與 Manacher 算法類似,都是利用了雙指針的思想。在考慮到 $z[i]$ 時,假設 $z[0],z[1],\ldots,z[i - 1]$ 的答案已經得出,並且當前最大的 $k + z[k] - 1(k=0,1,\ldots,i-1)$ 記為 $r$,並記此時的 $k$ 為 $l$,那麼現在有兩種情況:

1. 若 $i\leq r$,那麼就有 $s[k - l] = s[k]$,$(k\in [i,r]\cap\mathbb{N})$,所以若 $z[i-l]<(r-i+1)$,那麼 $z[i]=z[i - l]$;否則暴力地擴張 $r$,檢查 $s[k]=s[k-r]$ ,$(k > r)$。 2. 若 $i > r$,那麼和第一種情況的第二種子情況一樣,暴力擴張。 由於 $r$ 的單向擴張知該算法複雜度為 $O(n)$。

C++ 實現如下:

1
2
3
4
5
6
7
8
9
10
11
vector<int> z_fun(string s) {
int n = s.size();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
int k = (i <= r && z[i - l] < (r - i + 1)) ? z[i - l] : max(0ll, r - i + 1);
while (i + k < n && s[k] == s[i + k]) ++k;
z[i] = k--;
if (i + k > r) l = i, r = i + k;
}
return z;
}

學習這個算法是因為昨天訓練時做到 2018 年 ICPC 南京賽區 M 題,只想到了用前綴函數 $\pi$ 結果誤入歧途。後來發現只要求一下 $z$ 的前綴和就行了。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×