Omówienie zadania Oceny

Szczegółowe omówienie zadania Oceny
Autor zadania: Kacper Omielańczyk
Zadanie Oceny ćwiczy 2 podejścia:
* Hashe
   * Binary Search
Sposób liczenia hashy jest dokładnie wytłumaczony w filmie:
który jest omówieniem zadania Subwords:
Hashe to jedno z najważniejszych podejść algorytmicznych:
https://tiny.pl/7hl83
——-
Kod C++ programu Oceny, który jest omówiony w powyższym filmie i który otrzymuje 100%

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+50;
const ll P1=313LL;
const ll P2=97LL;
const ll M1=1000LL*1000LL*1000LL+21LL;
const ll M2=1000LL*1000LL*1000LL+9LL;
char Szablon[N];
char Wzorzec[N];
ll Potegi1[N];
ll Potegi2[N];
ll HaszSzablon1[N];
ll HaszSzablon2[N];
ll HaszWzorzec1[N];
ll HaszWzorzec2[N];
void LiczPotegi(){
Potegi1[0]=Potegi2[0]=1LL;
for(int i=1; i<N; i++){
Potegi1[i]=(Potegi1[i-1]*P1)%M1;
Potegi2[i]=(Potegi2[i-1]*P2)%M2;
}
}
void LiczHasze(int n, int m){
for(int i=1; i<=n; i++){
HaszSzablon1[i]=(HaszSzablon1[i-1]+(ll)(Szablon[i])*Potegi1[i])%M1;
HaszSzablon2[i]=(HaszSzablon2[i-1]+(ll)(Szablon[i])*Potegi2[i])%M2;
HaszWzorzec1[i]=(HaszWzorzec1[i-1]+(ll)(Wzorzec[i])*Potegi1[i])%M1;
HaszWzorzec2[i]=(HaszWzorzec2[i-1]+(ll)(Wzorzec[i])*Potegi2[i])%M2;
}
}
int CzyRowne(int p1, int k1, int p2, int k2){
ll h1, h2, h3, h4;
h1=(HaszSzablon1[k1]-HaszSzablon1[p1-1]+M1)%M1;
h2=(HaszSzablon2[k1]-HaszSzablon2[p1-1]+M2)%M2;
h3=HaszWzorzec1[k2];
h4=HaszWzorzec2[k2];
h3=h3*Potegi1[k1-k2]%M1;
h4=h4*Potegi2[k1-k2]%M2;
if(h1==h3 && h2==h4) return 1;
return 0;
}
int JakDlugoRowne(int pocz, int n, int m){
if(Szablon[pocz]!=Wzorzec[1]) return 0;
int p, k, s;
p=1; k=min(n-pocz+1, m);
while(p<k){
s=(p+k+1)/2;
if( CzyRowne(pocz, pocz+s-1, 1, s) ) p=s;
else k=s-1;
}
return p;
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
LiczPotegi();
int n, m;
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>Szablon[i];
for(int i=1; i<=m; i++) cin>>Wzorzec[i];
LiczHasze(n, m);
int wynik=0;
for(int i=1; i<=n; i++)	wynik=max(wynik, JakDlugoRowne(i, n, m));
cout<<wynik<<"\n";
return 0;
}
Link do pliku z kodem C++ zadania Oceny 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz