Séquence de Serrure et de Clé#12236
Se connecter

Séquence de Serrure et de Clé (Corrigé)

Auteur du problème :

Imran AKKI

Préparé par :

Imran AKKI

Édité par :

Hasan Saleh (MathModel)

Solution Nous avons besoin de deux extrémités égales et de caractères distincts deux à deux strictement entre elles. De façon équivalente : trouver l < r avec s_l = s_r tel que la sous-chaîne s[l+1;r-1] = s_{l+1}s_{l+2}...s_{r-1} contienne au moins lettres distinctes, et parmi toutes ces paires retourner celle minimisant r-l+1.

Remarquez que pour une extrémité gauche fixée et un caractère fixé c = s_l, si se déplace vers la droite, le nombre de lettres distinctes dans (l,r) est non décroissant quand avance. Cette monotonie nous permet de faire une recherche dichotomique sur la plus petite valeur satisfaisant la condition des lettres distinctes pour chaque .

On peut compter les occurrences d'un caractère en en utilisant des tableaux de fréquences préfixées sur les 26 lettres minuscules comme , puis pour chaque lettre apparaissant au moins deux fois :

  1. Pour chaque indice d'occurrence (occurrence gauche), effectuer une recherche dichotomique parmi les occurrences suivantes \text{pos}[c][\text{mid}] pour le plus petit tel que la sous-chaîne intermédiaire s[i+1;r-1] contienne lettres distinctes.

  2. Utiliser pour compter les lettres distinctes dans cette sous-chaîne intermédiaire ; dès que distinctes sont trouvées.

  3. Garder en mémoire la longueur minimale de la sous-chaîne r - i + 1 et les extrémités correspondantes.

// Author: Imran AKKI (imranakki)
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lp(i, a, n) for (ll i = a; i < n; i++)
#define MAXN 1000005
#define MOD (ll)(1e9 + 7)
using namespace std;

void solve()
{
    ll n, k; cin >> n >> k;
    string s; cin >> s;

    // 1-based indexing !
    vector<vector<ll>> pre(26, vector<ll>(n + 2, 0));
    for(ll d = 0; d < 26; d++) {
        for(ll i = 0; i < n; i++) {
            pre[d][i + 1] = pre[d][i] + ((s[i] - 'a') == d);
        }
    }

    vector<ll> pos[26];
    for(ll i = 0; i < n; i++){
        pos[s[i] - 'a'].push_back(i);
    }

    auto can = [&](ll i, ll l) {
        // i and l are 0-indexed
        if(l - i < k + 1) return false;
        ll distinct = 0;
        for(ll d = 0; d < 26; d++) {
            if(pre[d][l] - pre[d][i + 1] > 0) {
                distinct++;
                if(distinct >= k){
                    return true;
                }
            }
        }
        return false;
    };
    ll bestLen = INT_MAX;
    ll bestI = -1, bestJ = -1;
    for(ll c = 0; c < 26; c++) {
        auto &P = pos[c];
        ll m = P.size();
        if(m < 2) continue;

        for(ll x = 0; x < m - 1; x++) {
            ll i = P[x];
            ll l = x + 1, r = m - 1;
            ll best = -1;
            while(l <= r) {
                ll mid = (l + r) >> 1;
                if(can(i, P[mid])) {
                    best = mid;
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            if(best != -1  && can(i, P[best]) && P[best] - i + 1 < bestLen) {
                bestLen = min(bestLen, P[best] - i + 1);
                bestI = i;
                bestJ = P[best];
            }
        }
    }

    if(bestI != -1) {
        cout << "YES\n";
        cout << bestI + 1 << " " << bestJ + 1 << "\n";
    } else {
        cout << "NO\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t; cin >> t;
    while(t--) solve();
    return 0;
}
C++

Complexité : \mathcal{O}(n \cdot 26 \cdot \log n)