Neka je dat rečnik od \(n\) reči. Upit je niska za koji treba ispisati sve reči iz rečnika za koje je taj upit prefiks.
Sa standardnog ulaza se učitavaju celi brojevi \(n\) i \(q\), a zatim i \(n\) reči rečnika. Nakon toga, učitava se \(q\) upita, svaki u zasebnom redu.
Za svaki od upita, na standardni izlaz, ispisati sve reči iz rečnika za koje je on prefiks.
5 3 code coder codecs coding coders cod code co codd
code coder codecs coders code coder codecs coding coders cod
Jedan pristup podrazumeva da za svaki upit i svaku reč iz rečnika proverimo da li je upit prefiks od reči. Kako broj upita može biti mnogo veći od broja reči u rečniku, bolje rešenje se dobija ako prvo pretprocesiramo rečnik, tako da za dati upit možemo efikasno da pronađemo sve reči kojima je on prefiks. Da bi ta operacija bila efikasna, zgodno je da za sve prefikse, svih reči iz rečnika, čuvamo listu koja će sadržati reči sa tim prefiksom. Za tako nešto možemo iskoristiti mapu, gde je ključ prefiks, a vrednost lista reči koja ima kao prefiks svoj ključ. Složenost obrade upita je sada \(O(1)\), ako je mapa implementirana preko heš tabele, ili \(O(\log N)\), gde je \(N\) broj prefiksa nekog rečnika, ako je mapa implementirana preko balansiranog uređenog stabla. Pretprocesiranje rečnika podrazumeva da, za sve reči \(w\) iz rečnika, i za svaki njen prefiks \(\pi_w\), na listu reči sa ključem \(\pi_w\) dodamo \(w\). Složenost pretprocesiranja rečnika je \(O(n M)\), gde je \(M\) dužina najduže reči u prefiksu, ako je mapa implementirana preko heš tabele, odnosno \(O(n M \log N)\), ako je mapa implementirana preko balansiranog uređenog stabla. Tada je ukupna složenost algoritma \(O(n M + q)\), ako je mapa implementirana preko heš tabele, odnosno \(O(n M \log N + q \log N)\), ako je mapa implementirana preko balansiranog uređenog stabla.
Bolje rešenje će biti predstavljeno u nastavku kursa.
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
int main(void)
{
int n, q;
std::cin >> n >> q;
map<string, vector<string>> autocomplete;
for (int i = 0; i < n; i++) {
string word;
cin >> word;
for (int i = 0; i <= word.size(); i++) {
autocomplete[word.substr(0, i)].push_back(word);
}
}
for (int i = 0; i < q; i++) {
string query;
cin >> query;
for (auto word : autocomplete[query]) {
cout << word << " ";
}
cout << endl;
}
return 0;
}