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)$.

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. Giữ khung $[l, r)$: đoạn khớp tiền tố có đầu phải xa nhất đã tìm được, tức $s[l..r)$ trùng $s[0..r - l)$. Vị trí $i$ nằm trong khung thì đã biết trước một phần độ dài khớp, chỉ so tiếp từ đó.

Bước 1: mượn kết quả cũ. $i < r$ thì $s[i..r)$ trùng $s[i - l..r - l)$, mà ở vị trí $i - l$ đã biết $z[i - l]$. Lấy min với r - i vì ngoài khung chưa biết gì.

if (i < r) z[i] = min(r - i, z[i - l]);

Bước 2: so tiếp và dời khung. So từng ký tự; đoạn khớp vươn xa hơn r thì dời khung về $i$. Mỗi lần so thành công khi $i + z[i] \ge r$ là một ký tự mới ngoài khung, nên tổng số lần so thêm không quá $n$.

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];

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 bằng xâu ghép

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ỳ đọc từ Z

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ụViền Của Chuỗi

Đề. Xâu dài tới $10^6$. In độ dài mọi viền (ngắn hơn cả xâu) theo thứ tự tăng dần, không có thì in 0.

Lời giải. z[i] == n - i nghĩa là hậu tố bắt đầu ở $i$ khớp trọn với tiền tố cùng độ dài: nó là một viền dài $n - i$. Duyệt $i$ giảm dần thì độ dài tăng dần, in đúng thứ tự. Bỏ $i = 0$ vì đó là cả xâu.

for (ll i = n - 1; i >= 1; i--)
    if (z[i] == n - i) {
        cout << n - i << ' ';
        any = 1;
    }

#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);
    bool any = 0;
    for (ll i = n - 1; i >= 1; i--)
        if (z[i] == n - i) {
            cout << n - i << ' ';
            any = 1;
        }
    if (!any) cout << 0;
    cout << '\n';
}

ChạyInputabcababcab

Output2 5

$O(n)$.

Ví dụNhịp Lặp Khuyết

Đề. Xâu dài tới $10^6$. In mọi chu kỳ $p$ (bản cuối được phép bị cắt) theo thứ tự tăng dần.

Lời giải. $p$ là chu kỳ 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: z[p] == n - p. Đây cũng chính là điều kiện có viền dài $n - p$. $n$ luôn là chu kỳ (không có cặp nào để kiểm), in ở cuối.

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

#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);
    for (ll p = 1; p < n; p++)
        if (z[p] == n - p) cout << p << ' ';
    cout << n << '\n';
}

ChạyInputabababa

Output2 4 6 7

$O(n)$.

Đếm lần xuất hiện của mọi tiền tố

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 xâu bằng các 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|)$.