Z Function

Hàm Z và hộp

Duyệt $i$ từ 1 tới $n - 1$, giữ hộp $[l, r)$: đoạn khớp với tiền tố có đầu phải $r$ xa nhất đã tìm được, tức $s[l..r) = s[0..r-l)$. Nếu $i < r$, vị trí $i$ nằm trong hộp nên đoạn bắt đầu tại $i$ giống đoạn bắt đầu tại $i - l$ của tiền tố, tới hết hộp: lấy sẵn $z[i] = \min(r - i,\ z[i - l])$. Rồi so tiếp từng ký tự từ $i + z[i]$ ra ngoài. Nếu đoạn mới vượt quá $r$ thì dời hộp thành $[i, i + z[i])$.

Mỗi phép so sánh thành công làm $r$ tăng 1 (vì so ngoài hộp), còn mỗi $i$ có nhiều nhất một phép so sánh hỏng. $r$ không vượt $n$, nên tổng số phép so sánh là $O(n)$. Bỏ hộp đi, so lại từ đầu ở mỗi $i$, thì trên xâu ngẫu nhiên vẫn nhanh vì mỗi lần chỉ khớp vài ký tự; nhưng xâu toàn một chữ lại cho $O(n^2)$:

Hộp nhanh gấp hàng nghìn lần ở đúng loại test mà người ra đề hay cài.

void zfunc(string &s, ll z[]) {
    ll n = s.size();
    z[0] = n;
    for (ll i = 1, l = 0, r = 0; i < n; i++) {
        z[i] = 0;
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
}

Ví dụDấu Vết Tiền Tố

Đề. Xâu $S$ dài tới $5 \cdot 10^5$. In mảng $z$ với $z[0] = n$.

Lời giải. Đúng hàm zfunc ở trên; z[0] = n theo quy ước của đề.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 5e5 + 5;
ll z[N];
string s;

void zfunc(string &s, ll z[]) {
    ll n = s.size();
    z[0] = n;
    for (ll i = 1, l = 0, r = 0; i < n; i++) {
        z[i] = 0;
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    zfunc(s, z);
    for (ll i = 0; i < (ll)s.size(); i++) cout << z[i] << ' ';
    cout << '\n';
}

ChạyInputabacaba

Output7 0 1 0 3 0 1

$O(n)$.

Tìm mẫu

Muốn tìm mẫu $P$ trong văn bản $T$, tính hàm Z của $P + \# + T$ với # không có trong hai xâu. Ở vị trí thuộc phần $T$, $z$ bị chặn bởi $|P|$ vì không đoạn nào vượt qua # được; $z = |P|$ đúng khi $P$ xuất hiện ở đó. Cả bài $O(|P| + |T|)$, bộ nhớ cho xâu ghép.

Ví dụCác Vị Trí Khớp

Đề. Văn bản $A$ và mẫu $B$, mỗi xâu dài tới $10^6$. In mọi vị trí (đánh số từ 1) mà $B$ bắt đầu trong $A$, kể cả chồng lấn; không có thì in 0.

Lời giải. Ghép mẫu, một ký tự ngăn cách và văn bản: $s = B + \# + A$. # không có trong hai xâu, nên ở mọi vị trí thuộc phần $A$, giá trị $z$ không vượt $|B|$; $z[i] \ge |B|$ nghĩa là $B$ khớp trọn tại đó. Hàm zfunc như ví dụ trước.

Bước 1: quét phần văn bản. Vị trí $i$ của xâu ghép ứng với vị trí $i - |B|$ của $A$ khi đánh số từ 1.

for (ll i = m + 1; i < (ll)s.size(); i++)
    if (z[i] >= m) {
        cout << i - m << ' ';
        any = 1;
    }

Xâu ghép dài tới $2 \cdot 10^6 + 1$, mảng z khai báo đủ.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e6 + 5;
ll z[N];
string a, b;

void zfunc(string &s, ll z[]) {
    ll n = s.size();
    z[0] = n;
    for (ll i = 1, l = 0, r = 0; i < n; i++) {
        z[i] = 0;
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> a >> b;
    string s = b + "#" + a;
    zfunc(s, z);
    ll m = b.size();
    bool any = 0;
    for (ll i = m + 1; i < (ll)s.size(); i++)
        if (z[i] >= m) {
            cout << i - m << ' ';
            any = 1;
        }
    if (!any) cout << 0;
    cout << '\n';
}

ChạyInputbananana
ana

Output2 4 6

$O(|A| + |B|)$.

Viền và chu kỳ

Hậu tố bắt đầu tại $i$ là một viền (vừa là tiền tố, vừa là hậu tố) khi và chỉ khi nó khớp với tiền tố tới hết xâu: $z[i] = n - i$. Viền đó dài $n - i$. Một số $p < n$ là chu kỳ của xâu khi $s_j = s_{j-p}$ với mọi $j \ge p$, tức hậu tố từ $p$ trùng tiền tố cùng độ dài: lại là $z[p] = n - p$. Vậy chu kỳ $p$ và viền dài $n - p$ là một (như bài 21), và $n$ luôn là chu kỳ. Liệt kê tất cả chỉ cần một vòng qua mảng $z$, ví dụ in mọi chu kỳ theo thứ tự tăng:

for (ll p = 1; p < n; p++)
    if (z[p] == n - p) cout << p << ' ';
cout << n << '\n';

Đếm lần xuất hiện

Tiền tố dài $L$ xuất hiện tại vị trí $i$ khi và chỉ khi $z[i] \ge L$. Vậy số lần xuất hiện của mọi tiền tố tính một lượt: đếm $cnt[v]$ là số vị trí có $z[i] = v$, rồi cộng dồn từ $v$ lớn xuống: số vị trí có $z \ge L$. Kết hợp với điều kiện viền ($z[n - L] = L$) cho các bài “tiền tố vừa là hậu tố, xuất hiện bao nhiêu lần”, “viền dài nhất còn xuất hiện ở giữa”.

Ví dụBiên Và Số Lần Xuất Hiện

Đề. Xâu dài tới $10^5$. Với mọi độ dài $L$ mà tiền tố dài $L$ cũng là hậu tố (kể cả cả xâu), in $L$ và số lần tiền tố đó xuất hiện, theo $L$ tăng dần.

Lời giải. Tiền tố dài $L$ xuất hiện tại $i$ khi và chỉ khi $z[i] \ge L$. Vậy số lần xuất hiện là số vị trí có $z \ge L$.

Bước 1: đếm theo giá trị $z$. cnt[v] là số vị trí có $z = v$, kể cả $z[0] = n$. Cộng dồn từ $v$ lớn xuống thì cnt[L] là số vị trí có $z \ge L$.

for (ll i = 0; i < n; i++) cnt[z[i]]++;
for (ll v = n - 1; v >= 0; v--) cnt[v] += cnt[v + 1];

Bước 2: chọn các viền. Tiền tố dài $L$ cũng là hậu tố khi z[n - L] == L; cả xâu ($L = n$) luôn thỏa và xuất hiện 1 lần.

for (ll L = 1; L <= n; L++)
    if (L == n || z[n - L] == L) res.push_back({L, cnt[L]});

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll z[N], cnt[N];
string s;

void zfunc(string &s, ll z[]) {
    ll n = s.size();
    z[0] = n;
    for (ll i = 1, l = 0, r = 0; i < n; i++) {
        z[i] = 0;
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    ll n = s.size();
    zfunc(s, z);
    for (ll i = 0; i < n; i++) cnt[z[i]]++;
    for (ll v = n - 1; v >= 0; v--) cnt[v] += cnt[v + 1];
    vector<pair<ll, ll>> res;
    for (ll L = 1; L <= n; L++)
        if (L == n || z[n - L] == L) res.push_back({L, cnt[L]});
    cout << res.size() << '\n';
    for (pair<ll, ll> p : res) cout << p.first << ' ' << p.second << '\n';
}

ChạyInputABACABA

Output3
1 4
3 2
7 1

$O(n)$.

Ví dụMật Khẩu Ba Lần

Đề. Xâu dài tới $10^6$. Tìm xâu dài nhất vừa là tiền tố, vừa là hậu tố, và còn xuất hiện ở một vị trí bắt đầu khác; không có thì in Just a legend.

Lời giải. Viền dài $L = n - i$ ứng với $z[i] = n - i$. Lần xuất hiện ở giữa phải bắt đầu tại một $j$ với $1 \le j < i$ và $z[j] \ge L$; bắt đầu từ $i$ trở đi thì không còn đủ $L$ ký tự trước cuối xâu (trừ chính viền). Duyệt $i$ tăng dần, giữ mx là $\max z[j]$ trên các $j < i$. $i$ tăng thì $L$ giảm, nên viền đầu tiên thỏa là dài nhất.

for (ll i = 1; i < n; i++) {
    if (z[i] == n - i && mx >= n - i) {
        cout << s.substr(0, n - i) << '\n';
        return 0;
    }
    mx = max(mx, z[i]);
}

mx cập nhật sau khi xét $i$, để chỉ tính các $j$ đứng trước.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e6 + 5;
ll z[N];
string s;

void zfunc(string &s, ll z[]) {
    ll n = s.size();
    z[0] = n;
    for (ll i = 1, l = 0, r = 0; i < n; i++) {
        z[i] = 0;
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    ll n = s.size();
    zfunc(s, z);
    ll mx = 0;
    for (ll i = 1; i < n; i++) {
        if (z[i] == n - i && mx >= n - i) {
            cout << s.substr(0, n - i) << '\n';
            return 0;
        }
        mx = max(mx, z[i]);
    }
    cout << "Just a legend\n";
}

ChạyInputaaaaa

Outputaaa

$O(n)$.

Ghép bằng tiền tố

Hàm Z của $S + \# + T$ cho, tại mỗi vị trí $i$ của $T$, độ dài $L_i$ của tiền tố dài nhất của $S$ bắt đầu ở đó. Mọi tiền tố ngắn hơn cũng bắt đầu được ở $i$. Vậy từ vị trí $i$ của $T$ có thể nhảy tới bất kỳ vị trí nào trong $(i, i + L_i]$ bằng một mảnh. Ghép $T$ bằng ít mảnh nhất là bài nhảy xa quen thuộc: duyệt theo từng “tầng” của số mảnh, mỗi tầng mở rộng tới vị trí xa nhất mà các điểm trong tầng trước nhảy tới được, $O(|T|)$.

Ví dụGhép Đích Từ Các Tiền Tố

Đề. Xâu $S$, $T$ dài tới $5 \cdot 10^5$. Ghép $T$ từ ít tiền tố của $S$ nhất (được dùng lại), hoặc in $-1$.

Lời giải. Từ vị trí $i$ của $T$, một mảnh là tiền tố của $S$ khớp tại $i$. Tiền tố dài nhất khớp tại $i$ là $L_i$, lấy từ hàm Z của $S + \# + T$; mọi tiền tố ngắn hơn cũng khớp, nên từ $i$ nhảy được tới bất kỳ vị trí nào trong $(i, i + L_i]$. Bài thành: đi từ 0 tới $|T|$ bằng ít bước nhảy nhất.

Bước 1: độ dài nhảy. z[m + 1 + i] là $L_i$.

Bước 2: tham lam theo tầng. cur là vị trí xa nhất tới được bằng ans mảnh, far là vị trí xa nhất tới được bằng thêm một mảnh từ các vị trí $\le i$. Khi $i$ chạm cur, mọi vị trí tới được bằng ans mảnh đã xét, nên phải dùng thêm một mảnh và đặt cur = far. Nếu far không vượt $i$ thì kẹt, in $-1$.

for (ll i = 0; i < n && cur < n; i++) {
    far = max(far, i + z[m + 1 + i]);
    if (i == cur) {
        if (far <= i) {
            cout << -1 << '\n';
            return 0;
        }
        ans++;
        cur = far;
    }
}

Mỗi tầng đi xa nhất có thể, nên số mảnh ít nhất.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e6 + 5;
ll z[N];
string a, t;

void zfunc(string &s, ll z[]) {
    ll n = s.size();
    z[0] = n;
    for (ll i = 1, l = 0, r = 0; i < n; i++) {
        z[i] = 0;
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> a >> t;
    string s = a + "#" + t;
    zfunc(s, z);
    ll m = a.size(), n = t.size(), ans = 0, cur = 0, far = 0;
    for (ll i = 0; i < n && cur < n; i++) {
        far = max(far, i + z[m + 1 + i]);
        if (i == cur) {
            if (far <= i) {
                cout << -1 << '\n';
                return 0;
            }
            ans++;
            cur = far;
        }
    }
    cout << ans << '\n';
}

ChạyInputaba
ababa

Output2

$O(|S| + |T|)$.