Omówienie zadania Oceny

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