Cod sursa(job #629482)

Utilizator alexandrab0507Alexandra Beldica alexandrab0507 Data 3 noiembrie 2011 14:02:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
// hash2.cpp : Defines the entry point for the console application.
//


#include <iostream>
#include <fstream>
#include <string>
 
#define p 73
#define max_n 2000001
#define mod1 100021
#define mod2 100007
 
using namespace std;

ifstream f;
ofstream g;
string a,b;
int na,nb,match[max_n],i,hashA1,hashA2,hashB1,hashB2,p1,p2;
int sol[max_n],nr;
 
int main () {
	f.open("strmatch.in");
	g.open("strmatch.out");
	f>>a;
	f>>b;
	na=a.length();
	nb=b.length();
	 
	if (na>nb) {
		g<<0;
		return 0;
	}
	 
	hashA1=hashA2=hashB1=hashB2=0;
	p1=p2=1;
	nr=0;
	for (i=0; i<na; i++){
		hashA1=(hashA1*p+a[i])%mod1;
		hashA2=(hashA2*p+a[i])%mod2;
		if (i) {
			p1=(p1*p)%mod1;
			p2=(p2*p)%mod2;
		}
	}
	for (i=0; i<na; i++) {
		hashB1=(hashB1*p+b[i])%mod1;
		hashB2=(hashB2*p+b[i])%mod2;
	}
	if (hashA1==hashB1 && hashA2==hashB2) {
		sol[0]=1;
		nr++;
	}
	 
	for (i=na; i<nb; i++) {
		hashB1=((hashB1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
		hashB2=((hashB2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
		 
		if (hashA1==hashB1 && hashA2==hashB2)
			sol[i-na+1]=1;
	}
	 
	nr=0;
	for (i=0; i<nb; i++)
		if (sol[i]==1) nr++;
	g<<nr<<"\n";
	if (nr>1000) nr=1000;
	int x=0;
	for (i=0; i<=nb && x<nr; i++)
		if (sol[i]) {
			g<<i<<" ";
			x++;
		}
	f.close();
	g.close();
	return 0;
}