Pagini recente » Cod sursa (job #1472909) | Cod sursa (job #2251651) | Cod sursa (job #754432) | Cod sursa (job #1598116) | Cod sursa (job #1379840)
#include<fstream>
#include<string.h>
#define baza 128
#define h1 1000019
#define h2 1000023
using namespace std;
fstream f1,f2;
char A[2000002];
char B[2000002];
int P1,P2,i,hA1,hA2,hB1,hB2,M,N,k,x[2000002];
int nextHash1(int v, char x, char y)
{
v=((v-(P1*x)%h1+h1)*baza+y)%h1;
return v;
}
int nextHash2(int v, char x, char y)
{
v=((v-(P2*x)%h2+h2)*baza+y)%h2;
return v;
}
int main()
{
f1.open("strmatch.in",ios::in);
f2.open("strmatch.out",ios::out);
f1>>A>>B;
M=strlen(A);
N=strlen(B);
hA1=0; hA2=0; hB1=0; hB2=0; P1=1; P2=1;
//initializarea hashurilor
for (i=0;i<M;i++)
{
hA1=(hA1*baza+A[i])%h1;
hA2=(hA2*baza+A[i])%h2;
hB1=(hB1*baza+B[i])%h1;
hB2=(hB2*baza+B[i])%h2;
if (i)P1=(P1*baza)%h1;
if (i)P2=(P2*baza)%h2;
}
k=0;
if (hA1==hB1 && hA2==hB2){x[k]=0;k++;}
for (i=M;i<N;i++)
{
hB1=nextHash1(hB1,B[i-M],B[i]);
hB2=nextHash2(hB2,B[i-M],B[i]);
if (hA1==hB1 && hA2==hB2){x[k]=i-M+1;k++;}
}
f2<<k<<"\n";
for (i=0;i<k && i<1000;i++) f2<<x[i]<<" ";
f2.close();
f1.close();
return 0;
}