Omówienie zadania Subowords / Hashe

Omówienie zadania Subowords / Hashe

Szczegółowe omówienie zadania Subwords które jest ilustracją algorytmu liczenia hashy (skrótów)
Zadanie Subwords pokazuje jak wykorzystać algorytm liczenia hashy (skrótów) w konkursach informatycznych a także jego potężna zastosowania:
https://tiny.pl/7hl83
——-
Kod C++ programu Subwords, który jest omówiony w powyższym filmie i który otrzymuje 100%

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

const int MAKS_DLUGOSC_SLOWA = 1e3+7; //1007
const int MAKS_PDOSLOW = MAKS_DLUGOSC_SLOWA*MAKS_DLUGOSC_SLOWA;
const long long int MODULO1 = 1e9+7; //1000000007
const long long int MODULO2 = 1e9+9; //1000000009
const long long int g1 = 59;
const long long int g2 = 313;

string slowo;
long long int potegi1[MAKS_DLUGOSC_SLOWA];
long long int potegi2[MAKS_DLUGOSC_SLOWA];
long long int hash1_slowo[MAKS_DLUGOSC_SLOWA];
long long int hash2_slowo[MAKS_DLUGOSC_SLOWA];
pair < long long int, long long int> hashe_podslow[MAKS_PDOSLOW];

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 
 int liczba_roznych_podslow, ile_hashy_podslow;
 long long int wartosc_hasha, zmiana, hash1_podslowa, hash2_podslowa;
 int indeks_potega_wyrownujaca;
 int poczatek, koniec;
 int i,j;
 
 cin >> slowo;
 slowo = "#" + slowo;
 
//tablica 59^0 59^1 59^2 ... 
 potegi1[0] = 1;
 for (i=1; i<slowo.length(); ++i) {
    potegi1[i] = potegi1[i-1]*g1;
    potegi1[i] %= MODULO1;
 }
//tablica 313^0 313^1 313^2 ... 
 potegi2[0] = 1;
 for (i=1; i<slowo.length(); ++i) {
    potegi2[i] = potegi2[i-1]*g2;
    potegi2[i] %= MODULO2;
 }

//hashe numer 1 od pocztku do danej litery
 hash1_slowo[0] = (long long int)slowo[0];
 for (i=1; i<slowo.length(); ++i) {
 	hash1_slowo[i] = hash1_slowo[i-1];
 	zmiana = (long long int)slowo[i] * potegi1[i];
 	zmiana %= MODULO1;
 	hash1_slowo[i] += zmiana;
 	hash1_slowo[i] %= MODULO1;
 } 

//hashe numer 2 od pocztku do danej litery
 hash2_slowo[0] = (long long int)slowo[0];
 for (i=1; i<slowo.length(); ++i) {
 	hash2_slowo[i] = hash2_slowo[i-1];
 	zmiana = (long long int)slowo[i] * potegi2[i];
 	zmiana %= MODULO2;
 	hash2_slowo[i] += zmiana;
 	hash2_slowo[i] %= MODULO2;
 } 

//liczymy podwjne hashe kadego podsowa
 ile_hashy_podslow = 0;
 for (poczatek=1; poczatek<slowo.length(); ++poczatek) {
    for (koniec=poczatek; koniec<slowo.length(); ++koniec) {
       indeks_potega_wyrownujaca = slowo.length() - 1 - (koniec-poczatek) - poczatek;
//liczymy #1 podsowa
       hash1_podslowa = hash1_slowo[koniec] - hash1_slowo[poczatek-1];
       hash1_podslowa += MODULO1;
       hash1_podslowa %= MODULO1;
       hash1_podslowa *= potegi1[indeks_potega_wyrownujaca];
	   hash1_podslowa %= MODULO1;
//liczymy #2 podsowa
       hash2_podslowa = hash2_slowo[koniec] - hash2_slowo[poczatek-1];
       hash2_podslowa += MODULO2;
       hash2_podslowa %= MODULO2;
       hash2_podslowa *= potegi2[indeks_potega_wyrownujaca];
	   hash2_podslowa %= MODULO2;
//hash podsowa to #1 oraz #2 - czyli para hashy
	   hashe_podslow[ile_hashy_podslow] = make_pair(hash1_podslowa,hash2_podslowa);
	   ++ile_hashy_podslow;
    }
 } 

//sortujemy wszystkie hashe podsw
 sort ( hashe_podslow, hashe_podslow+ile_hashy_podslow) ; 

//liczymy ile jest rnych hashy - rnych podsw
 liczba_roznych_podslow = 1;
 for (i=1; i<ile_hashy_podslow; ++i) {
 	if (hashe_podslow[i-1] != hashe_podslow[i])
 	   ++liczba_roznych_podslow; //jeli para hashy jest rna od poprzedniej (w posorotwanej tablicy) to mamy nowe podsowo
 }

//wystarczy wypisa wynik
 cout << liczba_roznych_podslow << "\n";
  
 return 0;
}
Link do pliku z kodem C++ zadania "Subwords" 
————————
————————
————————
Kod C++ programu Subwords, który wykorzystuje pojedynczy hash i który otrzymuje 65% z uwagi na kolizje hashy:
#include <bits/stdc++.h>
using namespace std;

const int MAKS_DLUGOSC_SLOWA = 1e3+7; //1007
const int MAKS_PDOSLOW = MAKS_DLUGOSC_SLOWA*MAKS_DLUGOSC_SLOWA;
const long long int MODULO1 = 1e9+7; //1000000007
const long long int g1 = 59;

string slowo;
long long int potegi1[MAKS_DLUGOSC_SLOWA];
long long int hash1_slowo[MAKS_DLUGOSC_SLOWA];
long long int hashe_podslow[MAKS_PDOSLOW];

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 
 int liczba_roznych_podslow, ile_hashy_podslow;
 long long int wartosc_hasha, zmiana, hash1_podslowa, hash2_podslowa;
 int indeks_potega_wyrownujaca;
 int poczatek, koniec;
 int i,j;
 
 cin >> slowo;
 slowo = "#" + slowo;
 
//tablica 59^0 59^1 59^2 ... 
 potegi1[0] = 1;
 for (i=1; i<slowo.length(); ++i) {
    potegi1[i] = potegi1[i-1]*g1;
    potegi1[i] %= MODULO1;
 }

//hashe numer 1 od początku do danej litery
 hash1_slowo[0] = (long long int)slowo[0];
 for (i=1; i<slowo.length(); ++i) {
 	hash1_slowo[i] = hash1_slowo[i-1];
 	zmiana = (long long int)slowo[i] * potegi1[i];
 	zmiana %= MODULO1;
 	hash1_slowo[i] += zmiana;
 	hash1_slowo[i] %= MODULO1;
 } 

//liczymy pojedyncze hashe każdego podsłowa
 ile_hashy_podslow = 0;
 for (poczatek=1; poczatek<slowo.length(); ++poczatek) {
    for (koniec=poczatek; koniec<slowo.length(); ++koniec) {
       indeks_potega_wyrownujaca = slowo.length() - 1 - (koniec-poczatek) - poczatek;
//liczymy hash podsłowa
       hash1_podslowa = hash1_slowo[koniec] - hash1_slowo[poczatek-1];
       hash1_podslowa += MODULO1;
       hash1_podslowa %= MODULO1;
       hash1_podslowa *= potegi1[indeks_potega_wyrownujaca];
	   hash1_podslowa %= MODULO1;
//hashe wszystkich podsłów trzymamy w tablicy
	   hashe_podslow[ile_hashy_podslow] = hash1_podslowa;
	   ++ile_hashy_podslow;
    }
 } 

//sortujemy wszystkie hashe podsłów
 sort (hashe_podslow, hashe_podslow+ile_hashy_podslow) ; 

//liczymy ile jest różnych hashy - różnych podsłów
 liczba_roznych_podslow = 1;
 for (i=1; i<ile_hashy_podslow; ++i) {
 	if (hashe_podslow[i-1] != hashe_podslow[i])
 	   ++liczba_roznych_podslow; //jeśli aktualny hash różny od poprzedniego (w posorotwanej tablicy) to mamy nowe podsłowo
 }

//wystarczy wypisać wynik
 cout << liczba_roznych_podslow << "\n";
  
 return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz