Cod sursa(job #654975)

Utilizator nautilusCohal Alexandru nautilus Data 31 decembrie 2011 15:05:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define DMAX 2000010
#define PUTERE 127
#define PRIM1 100003
#define PRIM2 100019

char A[DMAX],B[DMAX];
int valA1,valA2,lungA;
int valB1,valB2,lungB;
int puteremax1=1,puteremax2=1,nrmatch;
bool pozmatch[DMAX];

void read()
{
 ifstream fin("strmatch.in");

 fin.get(A, DMAX);
 lungA = (int)strlen(A);
 fin.get();
 fin.get(B, DMAX);
 lungB = (int)strlen(B);

 fin.close();
}

void preprocesare()
{
 int i;
 for (i=0; i<lungA; ++i)
	{
	 valA1 = (valA1 * PUTERE + A[i]) % PRIM1;
	 valA2 = (valA2 * PUTERE + A[i]) % PRIM2;
	 valB1 = (valB1 * PUTERE + B[i]) % PRIM1;
	 valB2 = (valB2 * PUTERE + B[i]) % PRIM2;
	 if (i > 0)
		{
		 puteremax1 = (puteremax1 * PUTERE) % PRIM1;
		 puteremax2 = (puteremax2 * PUTERE) % PRIM2;
		}
	}
}

void solve()
{
 int i;
 if (valA1 == valB1 && valA2 == valB2)
	{
	 nrmatch++;
	 pozmatch[0] = 1;
	}

 for (i=1; i<=(int)(lungB - lungA); ++i)
	{
	 valB1 = ((valB1 - (B[i-1] * puteremax1) % PRIM1 + PRIM1) * PUTERE + B[i + lungA - 1]) % PRIM1;
	 valB2 = ((valB2 - (B[i-1] * puteremax2) % PRIM2 + PRIM2) * PUTERE + B[i + lungA - 1]) % PRIM2;
	 // termenul " + PRIM1 " se aplica pentru corectie, in cazul in care ceea ce am obtinut anterior este negativ, pentru a obtine un rezultat pozitiv
	 if (valA1 == valB1 && valA2 == valB2)
		{
		 nrmatch++;
		 pozmatch[i] = 1;
		}
	}
}

void write()
{
 int i=-1,j=0;
 ofstream fout("strmatch.out");

 fout<<nrmatch<<'\n';
 while (j < nrmatch && j < 1000)
	{
	 i++;
	 if (pozmatch[i] == 1)
		{
		 fout<<i<<" ";
		 j++;
		}
	}
 fout<<'\n';

 fout.close();
}

int main()
{
 read();
 preprocesare();
 solve();
 write();

 return 0;
}