Cod sursa(job #1507107)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 21 octombrie 2015 13:25:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <cstdint>

using namespace std;


#define ll long long

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

const int NMAX = 2000001;
const ll MOD1 = 1000000000000004;
const ll MOD2 = 1000000000000005;

int N; int M;

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


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

	vector<int> sol;

	ll p1 = 1; ll p2 = 1;

	ll interval = 'z' - '0';


	ll hashA1 = 0; ll hashB1 = 0;
	ll hashA2 = 0; ll hashB2 = 0;

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

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

	if(N > M) 
		return sol;

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

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

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

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

		hashB1 = (hashB1 - p1 * 1LL * (B[i - N] - '0' ) ) % MOD1;
		hashB2 = (hashB2 - p2 * 1LL * (B[i - N] - '0' ) ) % MOD2;

		if(hashB1 < 0)
			hashB1 += MOD1;

		if(hashB2 < 0) 
			hashB2 += MOD2;

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

	if(hashB1 == hashA1 && hashA2 == hashB2 )
			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 < 1000; ++i)
		fout << sol[i] << " " ;

	return 0;
}