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

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

Rezumat

Se dau n4n \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 11 și 6060

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 ll atunci pentru orice ii cuprins între 11 și ll putem afirma că există cel puțin o subsecvență OK de lungime ii Așadar, funcția booleană f(x)f(x) care ne spune dacă string-urile date au o subsecvență comună de lungime xx este monotonă. Pentru ili \le l returnează valoarea 11 iar pentru i>li \gt l avem f(i)=0f(i) = 0 Prin urmare, putem căuta binar rezultatul problemei în intervalul [1,60][1, 60] (Ni se garantează că l60l \le 60

Rămâne să verificăm dacă, pentru un xx fixat, există cel puțin o subsecvență OK de lungime xx 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 xx 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 22 iar răspunsul este maxim 6060 Astfel, hash-uirea unei subsecvențe va presupune transformarea acesteia într-un întreg ce încape pe long long int: Caracterul de pe poziția ii (de la dreapta, conform implementării) se va transforma într-un bit de 00 (în cazul lui a), sau într-unul de 11 (în cazul lui b), pe poziția ii î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 nn apare hash-ul respectiv drept subsecvență. Când unul dintre bitmask-uri devine 2n12^n - 1 ne oprim și returnăm true.

Problema Subsecvențe
#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 6060 din fiecare string dat. Ca să facem asta eficient, pentru string-ul ss de exemplu, luăm fiecare poziție ii de la 00 la len(s)1len(s) - 1 și inserăm în trie substring-ul care începe în ii și are lungimea min(len(s)i,60)\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 2n12^n - 1

Problema Subsecvențe
#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 nn suma lungimilor string-urilor date, soluția cu hashing are complexitatea O(nlognlog60)O(n \log n \log 60) Puteam înlocui map-ul cu un tabel de hashing (unordered_map), scăpând de factorul logn\log n dar câștigul ar fi fost mai mult teoretic. A doua soluție, cea cu trie, are complexitatea O(n60)O(n \cdot 60) Dacă n-am fi avut restricția cu 6060 complexitățile ar fi devenit O(nlog2n)O(n \log^2 n) și respectiv O(n2)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)O(n) Deci tot trie e baza.

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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii