Pagini recente » Statistici George Boboc (GeorgeBoboc2003) | Cod sursa (job #248069) | Cod sursa (job #2189675) | Cod sursa (job #2338545) | Cod sursa (job #2048648)
#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
int l, w;
char A [2000002];
char B [2000002];
bool init = 0;
int pos [1002];
int cnt = 0;
int P1 = 1, P2 = 1;
int H1 (char * w, int len)
{
int H = 0;
for(int i = 0; i < len; ++i)
{
H = (H * 57 + w[i]) % 100007;
if(i && !init)
{
P1 *= 57;
P1 %= 100007;
}
}
return H;
}
int H2 (char * w, int len)
{
int H = 0;
for(int i = 0; i < len; ++i)
{
H = (H * 57 + w[i]) % 100021;
if(i && !init)
{
P2 *= 57;
P2 %= 100021;
}
}
return H;
}
int naiv (char * mic, char * mare, int len)
{
for(int i = 0; i < len; ++i)
if(mic[i]!=mare[i])
return 0;
return 1;
}
int main()
{
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
in>>A>>B;
w = strlen(A);
l = strlen(B);
//cout<<w<<" "<<l<<"\n";
int hashw1, hashw2, temp1, temp2;
hashw1 = H1(A, w);
hashw2 = H2(A, w);
//cout<<hashw1<<" "<<hashw2<<"\n";
init = true;
int hs1, hs2;
hs1 = H1(B, w);
hs2 = H2(B, w);
//cout<<"Hashuri pt starea 0: "<<hs1<<" "<<hs2<<"\n";
for (int i = 0; i < l - w + 1; ++i)
{
//temp1 = H1(B + i, w);
//temp2 = H2(B + i, w);
if(hs1 == hashw1 && hs2 == hashw2)
{
//cout<<"HASH EGAL!\n";
if(naiv(A, B + i, w))
{
//cout<<"AVEM MATCH LA "<<i<<"\n";
if(cnt < 1000)
pos[cnt] = i;
++cnt;
//cout<<i<<" ";
}
}
//cout<<"Hashuri pt starea "<<i<<": "<<hs1<<" "<<hs2<<" (Expected "<<temp1<<" "<<temp2<<")\n";
hs1 = ((hs1 - (P1 * B[i]) % 100007 + 100007) * 57 + B[i + w]) % 100007;
hs2 = ((hs2 - (P2 * B[i]) % 100021 + 100021) * 57 + B[i + w]) % 100021;
}
out<<cnt<<"\n";
for (int i = 0; i < min(cnt, 1000); ++i)
out<<pos[i]<<" ";
return 0;
}