Cod sursa(job #2675995)

Utilizator Silviu45Dinca Silviu Silviu45 Data 23 noiembrie 2020 09:02:25
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <string> 
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

//RABIN-KARP 
//PRESUPUNEM CA HASH-UL ESTE SUMA CODURILOR ASCII ALE CARACTERELOR 
//CA SA FIE MAI SIMPLU DE INTELES DE MINE 

string A,B;
int hash_table[100000];
vector <int> positions;

int main(){
	fin >> A >> B;
	//cout << A <<" " << B << endl;
	unsigned int n = A.size();
	unsigned int m = B.size();
	
	//calculate hash of A string 
	int hash_A = 0,j=0;
	for(int i = 0; i < n; i++)
		hash_A += int(A[i]);
	//cout << hash_A << endl;
	
	hash_table[0] = int(B[0]);
	for(int i = 1; i < m-n+1; i++){
		hash_table[i] = int(B[i]) + hash_table[i-1];
		//if current window hash is equal with hash(A)
		//cout << "window-ul " << i << " "<<i-n+1<<" "<< hash_table[i] - hash_table[i-n+1] << "\n";
		if( i >= n){
			if(hash_table[i] - hash_table[i-n] == hash_A){
				for(j = 0; j < n; j++)
					if(B[i-n+1+j] != A[j])
						break;
				if(j == n)//daca a parcurs tot for-ull fara intrerupere chiar matching 
					positions.push_back(i-n+1);
			}
		}
	}
	fout << positions.size() << "\n";
	for(int i = 0; i < positions.size(); ++i)
		fout << positions[i] << " ";
	//for(int i = 0; i < m; i++)
	//	cout << hash_table[i] << " ";
	
	fin.close();
	fout.close();
	return 0;
}