Cod sursa(job #1251502)

Utilizator alexsimi66FMI Simandi Alexandru alexsimi66 Data 29 octombrie 2014 17:01:47
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

#define MAXN 2000001
#define MOD1 10007
#define MOD2 666013
#define PRIME1 27
#define PRIME2 29

int hashA1, hashA2;

int P1, P2;

char A[MAXN], B[MAXN];

void read(){
	ifstream fin("strmatch.in");
	fin.getline(A, MAXN);
	fin.getline(B, MAXN);

	fin.close();
}


void solve(){
	int v1 = 0;
	int v2 = 0;

	int NA = strlen(A);

	int P1 = 1, P2 = 1;

	for (int i = 0; i < NA; i++)
	{
		v1 = (v1 * PRIME1 + A[i]) % MOD1;
		v2 = (v2 * PRIME2 + A[i]) % MOD2;

		if (i != 0){
			P1 = (P1 * PRIME1) % MOD1;
			P2 = (P2 * PRIME2) % MOD2;
		}
	}
	//hasurile pentru A au fost facute

	int h1 = 0, h2 = 0;

	vector<int> poz;

	for (int i = 0; i < NA; i++)
	{
		h1 = (h1 * PRIME1 + B[i]) % MOD1;
		h2 = (h2 * PRIME2 + B[i]) % MOD2;
	}

	int NB = strlen(B);

	int cate = 0;


	for (int i = NA; i < NB; i++){
		h1 = ((h1 - (B[i - NA] * P1) % MOD1 + MOD1) * PRIME1 + B[i]) % MOD1;
		h2 = ((h2 - (B[i - NA] * P2) % MOD2 + MOD2) * PRIME2 + B[i]) % MOD2;
		
		if (h1 == v1 && h2 == v2){
			cate++;
			poz.push_back(i);
		}
	}

	ofstream fout("strmatch.out");
	fout << cate << "\n";

	int NV = poz.size();
	for (int i = 0; i < NV; i++){
		fout << poz[i] << " ";
	}

}






int main(){
	read();
	solve();

	return 0;
}