Synchronous Echo#13118

Synchronous Echo (Талдоо)

Solution

We need to count distinct nonempty strings $x$ that occur at least three times in both $s$ and $t$ , such that the positions of all their occurrences differ by the same shift.

Let $P_{x}$ P_x and $Q_{x}$ Q_x be the sets of ending positions of occurrences of $x$ in $s$ and $t$ , respectively.

The string $x$ is synchronous if and only if

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

|P_x|=|Q_x|\ge 3

and the two sets become identical after subtracting their minimum elements:

{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\}.

We will use a suffix automaton and polynomial hashing to check these conditions efficiently.

Suffix automaton

Build a suffix automaton for the string $s + # + t$ s+\#+t, where $#$ is a separator that does not occur in either input string.

Recall that each state $v$ of a suffix automaton represents all substring lengths in the interval

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

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

All substrings represented by the same state have exactly the same sets of ending positions.

Therefore, for every state $v$ , the number of its occurrences in $s$ and $t$ , as well as the relative positions of these occurrences, are identical for all represented substrings.

This means that either all substrings represented by a state are synchronous, or none of them are.

If a state satisfies the required conditions, its contribution to the answer is

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

len_v-len_{link_v}.

States corresponding to substrings containing the separator cannot have occurrences in both original strings, so they will not contribute to the answer.

Checking the occurrence positions

For every state $v$ , maintain the following information separately for $s$ and $t$ :

$c n t_{s}$ cnt_s, $c n t_{t}$ cnt_t — the numbers of occurrences;
$m n_{s}$ mn_s, $m n_{t}$ mn_t — the minimum ending positions;
$H_{s}$ H_s, $H_{t}$ H_t — polynomial hashes of the sets of ending positions.

For a fixed base $B$ and modulus $M$ , define

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.

We want to compare the occurrence positions after subtracting their minimum elements.

Instead of explicitly normalizing every position, we can compare

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.

Indeed, if the two sets differ only by a constant shift, multiplying their hashes by these powers makes them equal.

To make the probability of hash collisions negligible, we perform this comparison using two different moduli.

Thus, a state is accepted if

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

cnt_s=cnt_t\ge 3

and both hash comparisons succeed.

Calculating the information

While constructing the suffix automaton, every position of $s$ or $t$ corresponds to a terminal state.

For such a state, initially assign an occurrence count of $1$ , its ending position, and the corresponding power of $B$ to the appropriate string.

All other values are initially zero. Cloned states do not receive additional occurrences.

After constructing the automaton, propagate the information along suffix links from children to parents.

When merging the information of two states, we add their occurrence counts and hashes, and take the minimum of their ending positions.

This gives the required information for every state in linear time.

Finally, iterate over all states. For every state satisfying the conditions, add

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

len_v-len_{link_v}

to the answer.

Complexity Analysis

A suffix automaton for a string of length $∣ s ∣ + ∣ t ∣ + 1$ |s|+|t|+1 contains $O (∣ s ∣ + ∣ t ∣)$ O(|s|+|t|) states.

Constructing the automaton, propagating the information along suffix links, and checking every state all take linear time.

Therefore, the total time complexity is $O (∣ s ∣ + ∣ t ∣)$ O(|s|+|t|), and the space complexity is $O (∣ s ∣ + ∣ t ∣)$ O(|s|+|t|).

Implementation

#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();
}