Двократний підрядок#5465

Двократний підрядок (Розбір)

Solution

General Idea : We are given a string $S$ of length $n$ and an integer $k$ . We want to find any substring of length $k$ that appears at least twice. Since $n$ can reach $1 0^{5}$ 10^5, a brute force comparison of all substrings would be too slow. Therefore, we use Double Hashing with a Sliding Window to compare substrings efficiently in $O (1)$ time after preprocessing.

We first precompute powers of two hash bases. Then we build prefix hashes for the entire string. For every substring $S [i .. i + k - 1]$ S[i..i+k-1], we compute its hash using:

H (i, j) = H [j] - H [i - 1] \times p^{(j - i + 1)}

H(i, j) = H[j] - H[i-1] \times p^{(j-i+1)}

We store each hash in a map. If any hash appears twice, we immediately return that substring.

This guarantees:

$O (n)$ substring checks.
$O (1)$ comparison using hashing.
Very low collision probability using double hashing.

Overall complexity:

O (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(){
    string s; cin >> s;
    int k; cin >> k;
    int n = s.size();

    buildHash(s);

    map<pair<int,int>, int> mp;
    string ans = "NONE";
    string window = "";

    for(int i = 0; i < n; i++){
        window += s[i];

        if(window.size() == k){
            auto h = getHash(i - k + 1, i);
            mp[h]++;
            if(mp[h] == 2){
                ans = window;
                break;
            }
            window.erase(window.begin());
        }
    }

    cout << ans;
}

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