Підрядки-3#5094

Підрядки-3 (Розбір)

Solution

General Idea : We are given $K$ strings, each of length up to $1 0^{4}$ 10^4, and we need to find the longest substring common to all $K$ strings. A direct comparison of all substrings is too slow. Therefore, we use:

Binary Search on the answer length.
Double Rolling Hash to compare substrings efficiently.

Let $f$ be the minimum length among all $K$ strings. We binary search on the answer length $L$ in the range:

1 \leq L \leq f

1 \le L \le f

For a fixed length $L$ :

For each string, we generate all substrings of length $L$ .
We store their double hash values.
A substring is valid only if it appears in all $K$ strings.

The rolling hash of substring $S [l .. r]$ S[l..r] is computed as:

H (l, r) = H [r] - H [l - 1] \cdot p^{(r - l + 1)}

H(l, r) = H[r] - H[l-1] \cdot p^{(r-l+1)}

If at any length $L$ we find a substring that appears in all $K$ rows, we increase the search. Otherwise, we decrease it.

This guarantees:

$O (K \cdot n \cdot lo g n)$ \mathcal{O}(K \cdot n \cdot \log n) total complexity.
$O (1)$ substring comparison.
Very low probability of collisions using double hashing.

Overall complexity:

O (K \cdot n \cdot lo g n)

\mathcal{O}(K \cdot n \cdot \log n)


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

#define ll long long
#define Moageza ios::sync_with_stdio(false); cin.tie(nullptr);

const int N = 1e6 + 5;
const int base1 = 127, base2 = 131;
const int mod1 = 1e9 + 7, mod2 = 2e9 + 11;

int pw1[N], pw2[N];
pair<int,int> pre[N];

void init(){
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i < N; i++){
        pw1[i] = (1LL * pw1[i-1] * base1) % mod1;
        pw2[i] = (1LL * pw2[i-1] * base2) % mod2;
    }
}

void buildHash(string &s){
    int a = 0, b = 0;
    for(int i = 0; i < s.size(); i++){
        a = (1LL * a * base1 + s[i]) % mod1;
        b = (1LL * b * base2 + s[i]) % mod2;
        pre[i] = {a, b};
    }
}

pair<int,int> getHash(int l, int r){
    auto ret = pre[r];
    int sz = r - l + 1;
    if(l > 0){
        ret.first = (ret.first - 1LL * pre[l-1].first * pw1[sz] % mod1 + mod1) % mod1;
        ret.second = (ret.second - 1LL * pre[l-1].second * pw2[sz] % mod2 + mod2) % mod2;
    }
    return ret;
}

void solve(){
    int K; cin >> K;
    vector<string> v(K);
    int f = 10000;

    for(int i = 0; i < K; i++){
        cin >> v[i];
        f = min(f, (int)v[i].size());
    }

    int l = 1, r = f;
    string ans = "";

    while(l <= r){
        int mid = (l + r) / 2;
        map<pair<int,int>, int> mp;

        for(int i = 0; i < K; i++){
            map<pair<int,int>, int> used;
            buildHash(v[i]);
            int n = v[i].size();

            for(int j = 0; j + mid - 1 < n; j++){
                auto h = getHash(j, j + mid - 1);
                if(!used[h]){
                    used[h] = 1;
                    mp[h]++;
                    if(mp[h] == K){
                        ans = v[i].substr(j, mid);
                        break;
                    }
                }
            }
        }

        if((int)ans.size() == mid)
            l = mid + 1;
        else
            r = mid - 1;
    }

    cout << ans ;
}

int main(){
    Moageza
    init();
    solve();
    return 0;
}