Cod sursa(job #1506875)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 21 octombrie 2015 00:55:53
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMAX = 2000000;
const int MOD1 = 104234;
const int MOD2 = 124923;

int N; int M;

char A[NMAX]; char B[NMAX];


vector<int> RabinKarp(char* A, char* B) {

	vector<int> sol;

	int p1 = 1; int p2 = 1;

	int interval = 'z' - 'A' + 1;

	int hashA1 = 0; int hashB1 = 0;
	int hashA2 = 0; int hashB2 = 0;

	for(int i = 0 ; i < N; ++i) {

		hashA1 = (1LL * hashA1 * interval + 1LL * (A[i] - 'A')  ) % MOD1;
		hashA2 = (1LL * hashA2 * interval + 1LL * (A[i] - 'A')  ) % MOD2;
		
		if(i) {
			p1 = 1LL * p1 * interval % MOD1;
			p2 = 1LL * p2 * interval % MOD2;
		}
	}

	if(N > M) {
		sol.push_back(0);
		return sol;
	}

	for(int i = 0; i < N; ++i) {

		hashB1 = (1LL * hashB1 * interval + 1LL * (B[i] - 'A')  ) % MOD1;
		hashB2 = (1LL * hashB2 * interval + 1LL * (B[i] - 'A')  ) % MOD2;
		
	}

	for(int i = N; i < M; ++i) {

		if(hashB1 == hashA1 && hashA2 == hashB2 && sol.size() < 1000)
			sol.push_back(i - N);

		hashB1 = hashB1 - p1 * (B[i - N] - 'A');
		hashB2 = hashB2 - p2 * (B[i - N] - 'A');

		if(hashB1 < 0)
			hashB1 += MOD1;

		if(hashB2 < 0) 
			hashB2 += MOD2;

		hashB1 = ( 1LL * hashB1 * interval + 1LL * (B[i] - 'A') ) % MOD1;
		hashB2 = ( 1LL * hashB2 * interval + 1LL * (B[i] - 'A') ) % MOD2;
	}

	if(hashB1 == hashA1 && hashA2 == hashB2 && sol.size() < 1000)
			sol.push_back(M - N);

	return sol;

}


int main() {

	fin >> A;
	fin >> B;

	N = strlen(A);
	M = strlen(B);
	vector<int> sol;

	sol = RabinKarp(A, B);


	fout << sol.size()  << '\n'; 
	for(unsigned i = 0 ; i < sol.size(); ++i)
		fout << sol[i] << " " ;

	return 0;
}