Manacher Algorithm

IKiểm một xâu con có đối xứng không

Đánh số các ký tự của $s$ từ $1$ tới $n$ và viết $s[l..r]$ cho đoạn từ ký tự thứ $l$ tới ký tự thứ $r$. Gọi $t$ là xâu đảo của $s$, tức $t_i = s_{n+1-i}$; với $s$ = dabacab thì $t$ = bacabad. Đoạn $s[l..r]$ viết ngược chính là $t[n+1-r..n+1-l]$, nên $s[l..r]$ đối xứng khi và chỉ khi hai đoạn này bằng nhau. Có hash tiền tố của cả $s$ và $t$ (bài 1.10.1), việc đó là một phép so sánh hai số, tốn $O(1)$ sau $O(n)$ chuẩn bị.

Ví dụCửa Sổ Đối Xứng

Đề. Cho số nguyên $k$ và xâu $s$ gồm chữ thường, $2 \le k \le |s| \le 3 \cdot 10^4$. Đếm số cửa sổ gồm đúng $k$ ký tự liên tiếp của $s$ là xâu đối xứng; hai cửa sổ ở hai vị trí khác nhau được đếm riêng dù nội dung giống nhau.

Lời giải. Có $n - k + 1$ cửa sổ. Kiểm từng cửa sổ bằng cách so lần lượt các cặp ký tự đối nhau tốn $O(k)$, cả bài $O(nk)$. Với hash của $s$ và của $t$, mỗi cửa sổ chỉ còn một phép so sánh. Ta dùng modulo $2^{61} - 1$ với cơ số ngẫu nhiên và hàm mul như ở bài 1.10.1. Hash của $t$ dựng bằng cách đọc $s$ từ cuối về đầu.

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

const ull MOD = (1ULL << 61) - 1;
const ll N = 3e4 + 5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull B = rng() % (MOD - 1000) + 500, h[N], g[N], pw[N];
ll n, k;
string s;

ull mul(ull a, ull b) {
    __int128 t = (__int128)a * b;
    ull r = (ull)(t & MOD) + (ull)(t >> 61);
    return r >= MOD ? r - MOD : r;
}

ull get(ull f[], ll l, ll r) {
    return (f[r] + MOD - mul(f[l - 1], pw[r - l + 1])) % MOD;
}

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

    cin >> k >> s;
    n = s.size();
    pw[0] = 1;
    for (ll i = 1; i <= n; i++) {
        pw[i] = mul(pw[i - 1], B);
        h[i] = (mul(h[i - 1], B) + s[i - 1]) % MOD;
        g[i] = (mul(g[i - 1], B) + s[n - i]) % MOD;
    }
    ll ans = 0;
    for (ll l = 1; l + k - 1 <= n; l++) {
        ll r = l + k - 1;
        if (get(h, l, r) == get(g, n + 1 - r, n + 1 - l)) ans++;
    }
    cout << ans << '\n';
}

ChạyInput3
abacaba

Output3

Độ phức tạp: $O(n)$, với $n = 3 \cdot 10^4$ cần khoảng $10^5$ phép tính.

IIBán kính đối xứng tại mỗi tâm

Một xâu đối xứng độ dài lẻ có một ký tự ở giữa, một xâu độ dài chẵn có hai ký tự giữa bằng nhau. Bỏ ký tự đầu và ký tự cuối của một xâu đối xứng thì phần còn lại vẫn đối xứng, nên các xâu đối xứng cùng tâm lồng vào nhau như những vòng tròn đồng tâm. Với mỗi vị trí $i$, ta đặt hai đại lượng:

• $d_1[i]$ là số xâu đối xứng có độ dài lẻ với ký tự giữa là $s_i$. Xâu dài nhất trong số đó có độ dài $2 d_1[i] - 1$, và $d_1[i] \ge 1$ vì một ký tự luôn đối xứng.
• $d_2[i]$ là số xâu đối xứng có độ dài chẵn với hai ký tự giữa là $s_{i-1}$ và $s_i$. Xâu dài nhất có độ dài $2 d_2[i]$, và $d_2[i]$ có thể bằng $0$.

Ta gọi chung $d_1[i]$, $d_2[i]$ là bán kính của tâm tương ứng. Với $s$ = abaaba thì $d_1 = 1, 2, 1, 1, 2, 1$ và $d_2 = 0, 0, 0, 3, 0, 0$.

Cách dễ nghĩ ra nhất là mở rộng từng ký tự một cho mọi tâm:

for (ll i = 1; i <= n; i++) {
    d1[i] = 1;
    while (i - d1[i] >= 1 && i + d1[i] <= n && s[i - d1[i]] == s[i + d1[i]]) d1[i]++;
    while (i - d2[i] - 1 >= 1 && i + d2[i] <= n && s[i - d2[i] - 1] == s[i + d2[i]]) d2[i]++;
}

Độ phức tạp: $O(n^2)$ khi xâu gồm toàn một chữ cái, với $n = 10^6$ cần khoảng $5 \cdot 10^{11}$ phép tính.

Ta có thể thấy điểm lãng phí của cách làm này: bán kính $k$ mà đúng thì bán kính $k - 1$ cũng đúng, nên với một tâm cố định, ta chặt nhị phân được bán kính lớn nhất thay vì thử từng giá trị. Mỗi lần thử là kiểm một đoạn có đối xứng không, đã làm được trong $O(1)$ bằng hash ở mục trước.

Ví dụĐối Xứng Dài Nhất

Đề. Cho xâu $s$ dài $n \le 5 \cdot 10^4$, gồm các ký tự ASCII in được khác khoảng trắng. In độ dài lớn nhất của một xâu con liên tiếp đối xứng.

Lời giải. Với mỗi tâm lẻ $i$, bán kính $k$ nằm trong $[1, \min(i, n - i + 1)]$ và đoạn cần kiểm là $s[i-k+1..i+k-1]$. Với mỗi tâm chẵn $i$, bán kính $k$ nằm trong $[0, \min(i - 1, n - i + 1)]$ và đoạn cần kiểm là $s[i-k..i+k-1]$. Hàm pal(l, r) so hash của $s[l..r]$ với hash đoạn tương ứng trên xâu đảo. Đáp án là giá trị lớn nhất của $2 d_1[i] - 1$ và $2 d_2[i]$ trên mọi $i$.

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

const ull MOD = (1ULL << 61) - 1;
const ll N = 5e4 + 5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull B = rng() % (MOD - 1000) + 500, h[N], g[N], pw[N];
ll n;
string s;

ull mul(ull a, ull b) {
    __int128 t = (__int128)a * b;
    ull r = (ull)(t & MOD) + (ull)(t >> 61);
    return r >= MOD ? r - MOD : r;
}

ull get(ull f[], ll l, ll r) {
    return (f[r] + MOD - mul(f[l - 1], pw[r - l + 1])) % MOD;
}

bool pal(ll l, ll r) {
    return get(h, l, r) == get(g, n + 1 - r, n + 1 - l);
}

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

    cin >> n >> s;
    pw[0] = 1;
    for (ll i = 1; i <= n; i++) {
        pw[i] = mul(pw[i - 1], B);
        h[i] = (mul(h[i - 1], B) + s[i - 1]) % MOD;
        g[i] = (mul(g[i - 1], B) + s[n - i]) % MOD;
    }
    ll ans = 1;
    for (ll i = 1; i <= n; i++) {
        ll l = 1, r = min(i, n - i + 1), d1 = 1;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (pal(i - mid + 1, i + mid - 1)) l = (d1 = mid) + 1;
            else r = mid - 1;
        }
        l = 0, r = min(i - 1, n - i + 1);
        ll d2 = 0;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (pal(i - mid, i + mid - 1)) l = (d2 = mid) + 1;
            else r = mid - 1;
        }
        ans = max(ans, max(2 * d1 - 1, 2 * d2));
    }
    cout << ans << '\n';
}

ChạyInput6
cabbad

Output4

Độ phức tạp: $O(n \log n)$, với $n = 5 \cdot 10^4$ cần khoảng $1{,}6 \cdot 10^6$ lần so hash.

Cách này còn $\log n$ lần so hash ở mỗi tâm, và vì dùng hash nên có xác suất sai rất nhỏ. Mục sau bỏ được cả hai.

IIIThuật toán Manacher

Gộp tâm lẻ và tâm chẵn. Để khỏi viết mọi thứ hai lần, ta dựng xâu $u$ từ $s$ bằng cách đặt ký tự # vào trước ký tự đầu, giữa mọi cặp ký tự kề nhau và sau ký tự cuối; abba thành #a#b#b#a#, dài $m = 2n + 1$. Trong $u$ mọi tâm đều là một ký tự: tâm lẻ của $s$ là ký tự thật, tâm chẵn của $s$ là dấu # nằm giữa hai ký tự. Khi mở rộng, hai ký tự đem so luôn cùng chẵn hoặc cùng lẻ vị trí, nên dấu # không bao giờ bị so với ký tự thật, kể cả khi $s$ cũng có ký tự #.

Gọi $p[i]$ là bán kính lớn nhất của xâu đối xứng trong $u$ có tâm $i$, tức số lớn nhất $k$ để $u[i-k..i+k]$ đối xứng. Xâu lớn nhất đó luôn bắt đầu và kết thúc bằng #: nếu hai đầu là chữ thì hai ký tự kế bên là #, bằng nhau, nên còn mở rộng được. Vậy nó gồm $p[i] + 1$ dấu # và $p[i]$ ký tự thật, và $p[i]$ chính là độ dài xâu đối xứng dài nhất của $s$ có tâm đó. Với $u$ = #a#b#a#b# ta có $p = 0, 1, 0, 3, 0, 3, 0, 1, 0$.

Dùng lại bán kính của điểm đối xứng. Ta tính $p[i]$ lần lượt từ $i = 1$ tới $m$, và giữ xâu đối xứng $u[l..r]$ tìm được cho tới lúc này có đầu phải $r$ xa nhất. Khi tâm $i$ nằm trong xâu đó ($i \le r$), điểm $j = l + r - i$ đối xứng với $i$ qua tâm của $u[l..r]$. Phần $u[l..r]$ đọc xuôi hay ngược như nhau, nên mọi thứ quanh $i$, trong phạm vi còn nằm trong $[l, r]$, giống hệt quanh $j$.

Do đó $p[i]$ ít nhất bằng $\min(p[j], r - i)$, với $r - i$ là khoảng cách từ $i$ tới đầu phải $r$. Ta lấy giá trị này làm điểm xuất phát rồi mở rộng thêm từng ký tự như cách làm đơn giản. Nếu $p[j] < r - i$ thì phép mở rộng dừng ngay ở bước đầu; nếu không, $r - i$ ký tự đã được kiểm và ta chỉ cần xét các ký tự ngoài $r$.

ll l = 1, r = 0;
for (ll i = 1; i <= m; i++) {
    ll k = 0;
    if (i <= r) k = min(p[l + r - i], r - i);
    while (i - k - 1 >= 1 && i + k + 1 <= m && u[i - k - 1] == u[i + k + 1]) k++;
    p[i] = k;
    if (i + k > r) l = i - k, r = i + k;
}

Độ phức tạp: $O(m) = O(n)$, với $n = 10^6$ cần khoảng $4 \cdot 10^6$ phép tính.

Chương trình đầy đủ cho bài toán mở đầu in độ dài và một xâu đối xứng dài nhất. Nếu $p[i]$ lớn nhất tại tâm $i$ thì xâu đó là $u[i-p[i]..i+p[i]]$, bắt đầu ở ký tự thứ $(i - p[i] + 1)/2$ của $s$.

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

const ll N = 2e6 + 5;
ll n, m, p[N];
char u[N];
string s;

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

    cin >> s;
    n = s.size();
    u[++m] = '#';
    for (ll i = 0; i < n; i++) {
        u[++m] = s[i];
        u[++m] = '#';
    }
    ll l = 1, r = 0, best = 1;
    for (ll i = 1; i <= m; i++) {
        ll k = 0;
        if (i <= r) k = min(p[l + r - i], r - i);
        while (i - k - 1 >= 1 && i + k + 1 <= m && u[i - k - 1] == u[i + k + 1]) k++;
        p[i] = k;
        if (i + k > r) l = i - k, r = i + k;
        if (p[i] > p[best]) best = i;
    }
    ll st = (best - p[best] + 1) / 2;
    cout << p[best] << '\n' << s.substr(st - 1, p[best]) << '\n';
}

ChạyInputcabbad

Output4
abba

Độ phức tạp: $O(n)$, với $n = 10^6$ cần khoảng $4 \cdot 10^6$ phép tính.

IVXâu đối xứng ở cuối xâu

Một xâu con $s[a..n]$ (hậu tố) đối xứng khi nào? Trong $u$, nó là đoạn $u[2a-1..m]$ kết thúc ở dấu # cuối cùng, và tâm $i$ của nó thỏa $i + p[i] = m$: đoạn đối xứng tâm $i$ chạm tới tận đầu phải của $u$. Ngược lại, tâm $i$ nào có $i + p[i] = m$ cho một hậu tố đối xứng dài $p[i]$. Hậu tố đối xứng dài nhất ứng với tâm $i$ nhỏ nhất như vậy. Tương tự cho tiền tố, với điều kiện $i - p[i] = 1$.

Ví dụNối Đuôi Thành Đối Xứng

Đề. Mỗi dòng input là một xâu gồm chữ cái hoa và thường, dài tới $10^5$. Với mỗi xâu, chỉ được nối thêm ký tự vào cuối để được xâu đối xứng ngắn nhất, giữ nguyên xâu ban đầu ở đầu kết quả. In xâu đó.

Lời giải. Gọi $\ell$ là độ dài hậu tố đối xứng dài nhất của $s$. Khi nối đảo của $n - \ell$ ký tự đầu vào cuối, phần hậu tố đối xứng ở giữa vẫn đối xứng, phần đầu và phần nối thành hai nửa đối nhau. Số ký tự phải nối là $n - \ell$, nhỏ nhất khi $\ell$ lớn nhất. Ta chạy Manacher, tìm tâm $i$ nhỏ nhất có $i + p[i] = m$ và đặt $\ell = p[i]$. Với Abc, hậu tố đối xứng dài nhất là c, ta nối bA để được AbcbA.

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

const ll N = 2e5 + 5;
ll m, p[N];
char u[N];
string s;

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

    while (cin >> s) {
        ll n = s.size();
        m = 0;
        u[++m] = '#';
        for (ll i = 0; i < n; i++) {
            u[++m] = s[i];
            u[++m] = '#';
        }
        ll l = 1, r = 0;
        for (ll i = 1; i <= m; i++) {
            ll k = 0;
            if (i <= r) k = min(p[l + r - i], r - i);
            while (i - k - 1 >= 1 && i + k + 1 <= m && u[i - k - 1] == u[i + k + 1]) k++;
            p[i] = k;
            if (i + k > r) l = i - k, r = i + k;
        }
        ll c = 1;
        while (c + p[c] != m) c++;
        cout << s;
        for (ll j = n - p[c] - 1; j >= 0; j--) cout << s[j];
        cout << '\n';
    }
}

ChạyInputAbc
racecar

OutputAbcbA
racecar

Độ phức tạp: $O(n)$ cho mỗi xâu, với $n = 10^5$ cần khoảng $4 \cdot 10^5$ phép tính.

VĐếm xâu con đối xứng

Mỗi xâu con đối xứng có đúng một tâm, và các xâu đối xứng cùng tâm chính là số bán kính, nên tổng số xâu con đối xứng (đếm theo vị trí, hai xâu giống nhau ở hai vị trí khác nhau được đếm riêng) là $\sum_i (d_1[i] + d_2[i])$. Ta lấy được hai mảng này từ $p$: ký tự $s_i$ nằm ở vị trí $2i$ của $u$ và dấu # đứng ngay trước nó ở vị trí $2i - 1$, nên

với phép chia nguyên.

Đếm theo vị trí bắt đầu và kết thúc. Tâm lẻ $i$ cho các xâu đối xứng bắt đầu ở mọi vị trí trong $[i - d_1[i] + 1, i]$ và kết thúc ở mọi vị trí trong $[i, i + d_1[i] - 1]$, mỗi vị trí đúng một xâu. Tâm chẵn $i$ cho các xâu bắt đầu trong $[i - d_2[i], i - 1]$ và kết thúc trong $[i, i + d_2[i] - 1]$. Cộng 1 vào cả một đoạn, rồi lấy tổng tiền tố là mảng hiệu của bài 0.3. Ta được $st[a]$ là số xâu đối xứng bắt đầu tại $a$ và $en[b]$ là số xâu đối xứng kết thúc tại $b$.

Cặp xâu không giao nhau. Bài toán: cho xâu $s$ dài $n \le 10^5$, đếm số cặp $(A, B)$ của hai xâu con đối xứng sao cho $A$ kết thúc trước vị trí $B$ bắt đầu (chọn theo vị trí). Với mỗi vị trí bắt đầu $b$ của $B$, số $A$ hợp lệ là $en[1] + \dots + en[b-1]$, nên đáp án là $\sum_b st[b] \cdot (en[1] + \dots + en[b-1])$.

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

const ll N = 2e5 + 5;
ll n, m, p[N], d1[N], d2[N], st[N], en[N];
char u[N];
string s;

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

    cin >> s;
    n = s.size();
    u[++m] = '#';
    for (ll i = 0; i < n; i++) {
        u[++m] = s[i];
        u[++m] = '#';
    }
    ll l = 1, r = 0;
    for (ll i = 1; i <= m; i++) {
        ll k = 0;
        if (i <= r) k = min(p[l + r - i], r - i);
        while (i - k - 1 >= 1 && i + k + 1 <= m && u[i - k - 1] == u[i + k + 1]) k++;
        p[i] = k;
        if (i + k > r) l = i - k, r = i + k;
    }
    for (ll i = 1; i <= n; i++) {
        d1[i] = (p[2 * i] + 1) / 2;
        d2[i] = p[2 * i - 1] / 2;
        st[i - d1[i] + 1]++, st[i + 1]--;
        en[i]++, en[i + d1[i]]--;
        st[i - d2[i]]++, st[i]--;
        en[i]++, en[i + d2[i]]--;
    }
    for (ll i = 1; i <= n; i++) st[i] += st[i - 1], en[i] += en[i - 1];
    ll ans = 0, pre = 0;
    for (ll b = 1; b <= n; b++) {
        ans += st[b] * pre;
        pre += en[b];
    }
    cout << ans << '\n';
}

ChạyInputabaab

Output16

Độ phức tạp: $O(n)$, với $n = 10^5$ cần khoảng $10^6$ phép tính.