Problema Subsecvențe – OJI 2013, Clasa a 11-a

• Dificultate:
• Autor: Marius Stroe
• Online: InfoArena, PbInfo

Rezumat

Se dau $n \ge 4$ șiruri de caractere formate doar din literele a și b. Pentru a simplifica soluția, vom spune că o subsecvență este OK dacă se regăsește în fiecare dintre string-urile date. Să se determine lungimea maximă a unei subsecvențe OK. Se garantează că răspunsul este cuprins între $1$ și $60$

Soluție cu hashing

Prima soluție de 100 de puncte despre care vom discuta folosește căutare binară și hashing. În primul rând, se observă ușor că răspunsul problemei poate fi căutat binar. Dacă cea mai lungă subsecvență OK are lungimea $l$ atunci pentru orice $i$ cuprins între $1$ și $l$ putem afirma că există cel puțin o subsecvență OK de lungime $i$ Așadar, funcția booleană $f(x)$ care ne spune dacă string-urile date au o subsecvență comună de lungime $x$ este monotonă. Pentru $i \le l$ returnează valoarea $1$ iar pentru $i \gt l$ avem $f(i) = 0$ Prin urmare, putem căuta binar rezultatul problemei în intervalul $[1, 60]$ (Ni se garantează că $l \le 60$

Rămâne să verificăm dacă, pentru un $x$ fixat, există cel puțin o subsecvență OK de lungime $x$ Putem face asta în timp liniar folosind hashing. Mai exact rolling hash – tehnica din Algoritmul Rabin-Karp ce ne permite să calculăm eficient hash-ul fiecărei subsecvențe de lungime $x$ dintr-un string. În general, soluțiile cu hashing trebuie evitate din diverse motive. Uneori putem lua WA pentru că n-am ales un MOD și o bază potrivite, iar alteori putem lua TLE din cauza operației modulo, sau din cauza faptului că am folosind double hashing, tocmai pentru a scăpa de Wrong Answer.

Însă, la problema asta avem două restricții care ne scapă de aceste probleme. Alfabetul folosit are lungimea $2$ iar răspunsul este maxim $60$ Astfel, hash-uirea unei subsecvențe va presupune transformarea acesteia într-un întreg ce încape pe long long int: Caracterul de pe poziția $i$ (de la dreapta, conform implementării) se va transforma într-un bit de $0$ (în cazul lui a), sau într-unul de $1$ (în cazul lui b), pe poziția $i$ în hash-ul asociat.

În timp ce calculăm aceste hash-uri, reținem într-un map, pentru fiecare hash obținut, un bitmask care să ne spună în ce string-uri dintre cele $n$ apare hash-ul respectiv drept subsecvență. Când unul dintre bitmask-uri devine $2^n - 1$ ne oprim și returnăm true.

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

ifstream fin("subsecvente.in");
ofstream fout("subsecvente.out");

int main() {
   int n; fin >> n;
   vector<string> str(n);
   for (int i = 0; i < n; i++)
       fin >> str[i];

   auto check = [&](int len) {
       map<int64_t, int> mask;
       for (int i = 0; i < n; i++)
           if (int(str[i].size()) >= len) {
               int64_t hash = 0;
               for (int j = 0; j < len; j++)
                   hash = (hash << 1) + str[i][j] - 'a';
               mask[hash] |= (1 << i);
               if (mask[hash] == (1 << n) - 1)
                   return true;
               for (int j = len; j < int(str[i].size()); j++) {
                   hash = ((hash - (str[i][j - len] - 'a') * (1LL << (len - 1))) << 1) + str[i][j] - 'a';
                   mask[hash] |= (1 << i);
                   if (mask[hash] == (1 << n) - 1)
                       return true;
               }
           }
       return false;
   };

   int lo = 0, hi = 61;
   while (hi - lo > 1) {
       int md = (lo + hi) / 2;
       if (check(md))
           lo = md;
       else
           hi = md;
   }
   fout << lo << '\n';
   return 0;
}

Soluție cu trie

O soluție mai eficientă, și poate mai ușor de implementat, folosește structura de date numită trie. Dacă n-ați mai auzit de ea, nu-i nicio problemă, pentru că voi publica foarte curând un articol despre aceasta. Pe scurt, o trie este un arbore în care fiecare nod are maxim $\Sigma$ fii – câte unul pentru fiecare literă a alfabetului (de lungime $\Sigma$ Un astfel de arbore este folosit adesea pentru a stoca eficient o mulțime de string-uri, acestea putând fi obținute din citirea caracterelor aflate pe lanțul de la rădăcină la diverse noduri, numite frunze. Sunt foarte multe de spus despre trie, dar vom discuta în articolul respectiv.

Soluția presupune să construim o trie în care să inserăm fiecare subsecvență de lungime maxim $60$ din fiecare string dat. Ca să facem asta eficient, pentru string-ul $s$ de exemplu, luăm fiecare poziție $i$ de la $0$ la $len(s) - 1$ și inserăm în trie substring-ul care începe în $i$ și are lungimea $\min(len(s) - i, 60)$ Când inserăm acest substring, am inserat practic fiecare prefix al său, nemaifiind nevoie să-l inserăm pe fiecare în parte.

În fiecare nod din trie stocăm un bitmask în care, la fel ca în soluția precedentă, reținem din ce string-uri face parte subsecvența corespunzătoare nodului respectiv. Răspunsul va fi dat de valoarea maximă a adâncimilor nodurilor care au bitmask-ul egal cu $2^n - 1$

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

ifstream fin("subsecvente.in");
ofstream fout("subsecvente.out");

class Trie {
    struct Node {
        int mask = 0;
        int next[2] = {};
    };

    int n, ans = 0;
    vector<Node> trie{1};

public:
    Trie(int n) : n(n) { }
    int solve() { return ans; }

    void insert(const string& str, int id) {
        int node = 0;
        for (int i = 0; i < int(str.size()); i++) {
            if (!trie[node].next[str[i] - 'a']) {
                trie[node].next[str[i] - 'a'] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].next[str[i] - 'a'];
            trie[node].mask |= (1 << id);
            if (trie[node].mask == (1 << n) - 1)
                ans = max(ans, i + 1);
        }
    }
};

int main() {
    int n; fin >> n;
    Trie trie(n);
    for (int i = 0; i < n; i++) {
        string str; fin >> str;
        for (int j = 0; j < int(str.size()); j++)
            trie.insert(str.substr(j, min(int(str.size() - j, 60))), i);
    }
    fout << trie.solve() << '\n';
    return 0;
}

Concluzie

Dacă notăm cu $n$ suma lungimilor string-urilor date, soluția cu hashing are complexitatea $O(n \log n \log 60)$ Puteam înlocui map-ul cu un tabel de hashing (unordered_map), scăpând de factorul $\log n$ dar câștigul ar fi fost mai mult teoretic. A doua soluție, cea cu trie, are complexitatea $O(n \cdot 60)$ Dacă n-am fi avut restricția cu $60$ complexitățile ar fi devenit $O(n \log^2 n)$ și respectiv $O(n^2)$ Prin urmare, soluția cu hashing ar fi fost mult mai rapidă. Însă, există două structuri de date, Suffix Tree și Suffix Automata, ambele bazate pe trie, care ne-ar fi permis să rezolvăm problema în $O(n)$ Deci tot trie e baza.

Dacă ai vreo nedumerire cu privire la problema Subsecvențe, lasă un comentariu și te voi ajuta