Cod sursa(job #2380604)

Utilizator VadimCCurca Vadim VadimC Data 15 martie 2019 11:31:14
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 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;

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

vector<int> poz;

bool IsPrim(int x){
	int i;
	int sq = sqrt(x);
	if(x % 2 == 0) return 0;
	for(i = 3; i <= sq; i++)
		if(x % i == 0) return 0;
	return 1;
}

void RK();
bool verifica(int);

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

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

bool verifica(int x){
	for(int i = 0; i < m; i++) if(A[i] != B[i + x]) return 0;
	return 1;
}