Cod sursa(job #1124624)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 26 februarie 2014 12:59:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define nmax 2000005
#define mod1 666013
#define mod2 1000003
#define baza 73
using namespace std;

char sir1[nmax],sir2[nmax];
int l1,l2;
int h1a,h2a;
int h1b,h2b;
int bazapa=1,bazapb=1;
vector <int> r;

int main() {
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",sir1,sir2);
	l1 = strlen(sir1);
	l2 = strlen(sir2);
	h1a = sir1[0];
	h1b = sir1[0];
	h2a = sir2[0];
	h2b = sir2[0];
	for (int i=1;i<l1;i++) {
		bazapa = (bazapa*baza)%mod1;
		bazapb = (bazapb*baza)%mod2;
		h1a = (h1a*baza + sir1[i])%mod1;
		h1b = (h1b*baza + sir1[i])%mod2;
		h2a = (h2a*baza + sir2[i])%mod1;
		h2b = (h2b*baza + sir2[i])%mod2;
	}
	for (int i=l1;i<=l2;i++) {
		if (h1a == h2a && h1b == h2b) r.insert(r.begin(),i-l1);
		h2a = (((h2a - (sir2[i-l1]) * bazapa)%mod1 + mod1) * baza + sir2[i])%mod1; 
		h2b = (((h2b - (sir2[i-l1]) * bazapb)%mod2 + mod2) * baza + sir2[i])%mod2;
	}
	printf("%d\n",r.size());
	while (!r.empty()) {
		printf("%d ",r.back());
		r.pop_back();
	}
	return 0;
}