Cod sursa(job #1124681)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 26 februarie 2014 13:14:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 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.push_back(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());
	int nr = 1;
	for (vector <int> :: iterator it = r.begin();nr <= 1000 && it != r.end();nr++,it++) printf("%d ",*it);
	return 0;
}