Cod sursa(job #2380605)

Utilizator VadimCCurca Vadim VadimC Data 15 martie 2019 11:36:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

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

#define NMax 2000010
#define b 128
#define Mod 100003
#define Mod2 100019
int d1, d2;

string A, B;
int m, n;
int hashA1, hashA2;
int hash1, hash2;

vector<int> poz;

void RK();

int main(){
	fin >> A >> B;
	RK();
}

void RK(){
	int i, k;
	m = A.size();
	n = B.size();
	d1 = d2 = 1;
	for(i = 0; i < m; i++){
		hashA1 = (hashA1 * b + A[i]) % Mod;
		hashA2 = (hashA2 * b + A[i]) % Mod2;
		
		hash1 = (hash1 * b + B[i]) % Mod;
		hash2 = (hash2 * b + B[i]) % Mod2;
		
		if(i != 0){
			d1 = (d1 * b) % Mod;
			d2 = (d2 * b) % Mod2;
		}
	}
	if(hashA1 == hash1 && hashA2 == hash2) poz.push_back(0);
	for(k = 0; k < n - m; k++){
		hash1 = ((hash1 - (d1 * B[k]) % Mod + Mod) * b + B[k + m]) % Mod;
		hash2 = ((hash2 - (d2 * B[k]) % Mod2 + Mod2) * b + B[k + m]) % Mod2;
		if(hashA1 == hash1 && hashA2 == hash2) poz.push_back(k + 1);
	}
	
	fout << poz.size() << '\n';
	for(i = 0; i < poz.size() && i < 1000; i++) fout << poz[i] << ' ';
}