Cod sursa(job #819293)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 18 noiembrie 2012 19:48:42
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
#define mod1 666013
#define mod2 100007

char A[2000001], B[2000001];
int cod1A = 0, cod2A = 0, cod1B = 0, cod2B = 0;
int g1 = 1, g2 = 1, v[2000001];
ifstream in("strmatch.in"); ofstream out("strmatch.out");

void strVal(char *A, int n, int &cod1A, int &cod2A)
{
	int i;
	for (i=0;i<n;i++)
	{
		cod1A = (cod1A*73 + A[i])%mod1;
		cod2A = (cod2A*73 + A[i])%mod2;
	}
}

void gradVal(char *A, int &g1, int &g2)
{
	int i;
	for (i=1;i<strlen(A);i++)
	{
		g1 = (g1*73)%mod1;
		g2 = (g2*73)%mod2;
	}
}

int main()
{
	in>>A>>B;
	int nA = strlen(A), nB = strlen(B), i;
	if (nA > nB)
	{
		out<<"0\n";
		return 0;
	}
	
	strVal(A, nA, cod1A, cod2A);
	gradVal(A, g1, g2);
	strVal(B, nA, cod1B, cod2B);
	
	int cnt = 0;
	if (cod1A == cod1B && cod2A == cod2B)
		v[++cnt] = 0;
	
	for (i=nA; i<nB; i++)
	{
		cod1B = ((cod1B - (B[i - nA] * g1) % mod1 + mod1) * 73 + B[i]) % mod1;
		cod2B = ((cod2B - (B[i - nA] * g2) % mod2 + mod2) * 73 + B[i]) % mod2;
		if (cod1A == cod1B && cod2A == cod2B)
			v[++cnt] = i-nA+1;
	}
	
	out<<cnt<<"\n";
	for (i=1; i<=cnt && i<=1000; i++)
		out<<v[i]<<" ";
	return 0;	
	
}