Синхронне відлуння#13118

Синхронне відлуння (Розбір)

Розв'язок

Потрібно порахувати кількість різних непорожніх рядків $x$ , які зустрічаються щонайменше тричі в обох рядках $s$ і $t$ , причому позиції всіх їхніх входжень відрізняються на однаковий зсув.

Нехай $P_{x}$ P_x та $Q_{x}$ Q_x — множини позицій закінчення входжень рядка $x$ у рядки $s$ та $t$ відповідно.

Рядок $x$ є синхронним тоді й лише тоді, коли

∣ P_{x} ∣ = ∣ Q_{x} ∣ \geq 3

|P_x|=|Q_x|\ge 3

і ці множини стають однаковими після віднімання їхніх мінімальних елементів:

{p - min (P_{x}) ∣ p \in P_{x}} = {q - min (Q_{x}) ∣ q \in Q_{x}} .

\{p-\min(P_x)\mid p\in P_x\} = \{q-\min(Q_x)\mid q\in Q_x\}.

Для ефективної перевірки цих умов використаємо суфіксний автомат та поліноміальне хешування.

Суфіксний автомат

Побудуємо суфіксний автомат для рядка $s + # + t$ s+\#+t, де $#$ — роздільник, який не зустрічається в жодному з початкових рядків.

Нагадаємо, що кожен стан $v$ суфіксного автомата відповідає всім довжинам підрядків із проміжку

l e n_{l in k_{v}} + 1 \leq L \leq l e n_{v} .

len_{link_v}+1\le L\le len_v.

Усі підрядки, які відповідають одному стану, мають однакові множини позицій закінчення входжень.

Отже, для всіх підрядків одного стану кількість входжень у $s$ та $t$ , а також взаємне розташування цих входжень будуть однаковими.

Тому або всі підрядки, що відповідають стану, є синхронними, або жоден із них.

Якщо стан задовольняє необхідні умови, його внесок у відповідь дорівнює

l e n_{v} - l e n_{l in k_{v}} .

len_v-len_{link_v}.

Стани, які відповідають підрядкам із роздільником, не можуть мати входжень в обох початкових рядках, тому вони не впливають на відповідь.

Перевірка позицій входжень

Для кожного стану $v$ зберігатимемо окремо для $s$ та $t$ таку інформацію:

$c n t_{s}$ cnt_s, $c n t_{t}$ cnt_t — кількість входжень;
$m n_{s}$ mn_s, $m n_{t}$ mn_t — мінімальні позиції закінчення входжень;
$H_{s}$ H_s, $H_{t}$ H_t — поліноміальні хеші множин позицій закінчення входжень.

Для фіксованої основи $B$ та модуля $M$ визначимо

H_{s} = p \in P_{x} \sum B^{p} mod M,

H_s=\sum_{p\in P_x}B^p\bmod M,

H_{t} = q \in Q_{x} \sum B^{q} mod M .

H_t=\sum_{q\in Q_x}B^q\bmod M.

Нам потрібно порівняти позиції входжень після віднімання їхніх мінімальних елементів.

Замість явної нормалізації кожної позиції можемо перевірити рівність

H_{s} \cdot B^{m n_{t}} \equiv H_{t} \cdot B^{m n_{s}} (mod M) .

H_s\cdot B^{mn_t} \equiv H_t\cdot B^{mn_s} \pmod M.

Справді, якщо дві множини відрізняються лише на сталий зсув, множення їхніх хешів на відповідні степені зробить їх однаковими.

Щоб зробити ймовірність колізій хешів нехтовно малою, виконаємо цю перевірку за двома різними модулями.

Таким чином, стан задовольняє умови, якщо

c n t_{s} = c n t_{t} \geq 3

cnt_s=cnt_t\ge 3

і обидві перевірки хешів успішні.

Обчислення інформації

Під час побудови суфіксного автомата кожній позиції рядка $s$ або $t$ відповідає термінальний стан.

Для такого стану спочатку встановимо кількість входжень рівною $1$ , збережемо позицію закінчення та відповідний степінь $B$ для потрібного рядка.

Усі інші значення спочатку дорівнюють нулю. Клоновані стани не отримують додаткових входжень.

Після побудови автомата поширимо інформацію суфіксними посиланнями від дочірніх станів до батьківських.

Під час об'єднання інформації двох станів додаємо кількості входжень та хеші, а серед позицій закінчення вибираємо мінімальну.

Таким чином, за лінійний час отримаємо необхідну інформацію для кожного стану.

Нарешті, переберемо всі стани. Для кожного стану, який задовольняє умови, додамо до відповіді

l e n_{v} - l e n_{l in k_{v}} .

len_v-len_{link_v}.

Асимптотична складність

Суфіксний автомат для рядка довжини $∣ s ∣ + ∣ t ∣ + 1$ |s|+|t|+1 містить $O (∣ s ∣ + ∣ t ∣)$ O(|s|+|t|) станів.

Побудова автомата, поширення інформації суфіксними посиланнями та перевірка всіх станів виконуються за лінійний час.

Отже, загальна часова складність становить $O (∣ s ∣ + ∣ t ∣)$ O(|s|+|t|), а просторова — $O (∣ s ∣ + ∣ t ∣)$ O(|s|+|t|).

Реалізація

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

const int M1 = 1000000007;
const int M2 = 1000000009;
const int B = 911382323;

struct State {
    int to[27] = {};
    int link = -1, len = 0;
    int cs = 0, ct = 0;
    int ms = INT_MAX, mt = INT_MAX;
    int hs1 = 0, ht1 = 0, hs2 = 0, ht2 = 0;
};

void solve() {
    string s, t;
    cin >> s >> t;

    int n = max(s.size(), t.size());
    vector<int> pw1(n + 1, 1), pw2(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        pw1[i] = 1LL * pw1[i - 1] * B % M1;
        pw2[i] = 1LL * pw2[i - 1] * B % M2;
    }

    vector<State> st;
    st.reserve(2 * (s.size() + t.size() + 1) + 1);
    st.emplace_back();

    int last = 0;

    auto extend = [&](int c) {
        int cur = st.size();
        st.emplace_back();
        st[cur].len = st[last].len + 1;

        int p = last;

        while (p != -1 && st[p].to[c] == 0) {
            st[p].to[c] = cur;
            p = st[p].link;
        }

        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].to[c];

            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                State cl = st[q];
                cl.len = st[p].len + 1;
                cl.cs = cl.ct = 0;
                cl.hs1 = cl.ht1 = cl.hs2 = cl.ht2 = 0;
                cl.ms = cl.mt = INT_MAX;

                int clone = st.size();
                st.push_back(cl);

                while (p != -1 && st[p].to[c] == q) {
                    st[p].to[c] = clone;
                    p = st[p].link;
                }

                st[q].link = st[cur].link = clone;
            }
        }

        last = cur;
        return cur;
    };

    for (int i = 0; i < (int)s.size(); i++) {
        int v = extend(s[i] - 'a');

        st[v].cs = 1;
        st[v].ms = i;
        st[v].hs1 = pw1[i];
        st[v].hs2 = pw2[i];
    }

    extend(26);

    for (int i = 0; i < (int)t.size(); i++) {
        int v = extend(t[i] - 'a');

        st[v].ct = 1;
        st[v].mt = i;
        st[v].ht1 = pw1[i];
        st[v].ht2 = pw2[i];
    }

    int sz = st.size();
    vector<int> deg(sz);

    for (int v = 1; v < sz; v++) {
        deg[st[v].link]++;
    }

    queue<int> q;

    for (int v = 1; v < sz; v++) {
        if (deg[v] == 0) q.push(v);
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        int p = st[v].link;

        st[p].cs += st[v].cs;
        st[p].ct += st[v].ct;

        st[p].ms = min(st[p].ms, st[v].ms);
        st[p].mt = min(st[p].mt, st[v].mt);

        st[p].hs1 = (st[p].hs1 + st[v].hs1) % M1;
        st[p].ht1 = (st[p].ht1 + st[v].ht1) % M1;
        st[p].hs2 = (st[p].hs2 + st[v].hs2) % M2;
        st[p].ht2 = (st[p].ht2 + st[v].ht2) % M2;

        if (--deg[p] == 0 && p != 0) {
            q.push(p);
        }
    }

    ll ans = 0;

    for (int v = 1; v < sz; v++) {
        State &x = st[v];

        if (x.cs < 3 || x.cs != x.ct) continue;

        if (1LL * x.hs1 * pw1[x.mt] % M1 !=
            1LL * x.ht1 * pw1[x.ms] % M1) continue;

        if (1LL * x.hs2 * pw2[x.mt] % M2 !=
            1LL * x.ht2 * pw2[x.ms] % M2) continue;

        ans += x.len - st[x.link].len;
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}