Pagini recente » Monitorul de evaluare | Cod sursa (job #3357978) | Cod sursa (job #3357394) | Cod sursa (job #3357947) | Cod sursa (job #654888)
Cod sursa(job #654888)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define DMAX 2000010
#define PUTERE 73
#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;
}
}
}
int match(int pozstart)
{
int i=0;
while (i < lungA && A[i] == B[pozstart + i])
i++;
if ( i == lungA )
return 1;
return 0;
}
void solve()
{
int i;
if (valA1 == valB1 && valA2 == valB2)
if ( match(0) )
{
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)
if ( match(i) )
{
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;
}