Pagini recente » Cod sursa (job #2197389) | Cod sursa (job #1674826) | Cod sursa (job #1404366) | Cod sursa (job #2705527) | Cod sursa (job #564275)
Cod sursa(job #564275)
#include<fstream>
#include<string.h>
using namespace std;
fstream f1,f2;
char A[2000002];
char B[2000002];
int P,i,hA,hB,M,N,k,x[2000002];
int nextHash(int v, char x, char y)
{
v=((v-(P*x)%100019+100019)*73+y)%100019;
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);
hA=0; hB=0; P=1;
//initializarea hashurilor
for (i=0;i<M;i++)
{
hA=(hA*73+A[i])%100019;
hB=(hB*73+B[i])%100019;
if (i)P=(P*73)%100019;
}
k=0;
if (hA==hB){x[k]=0;k++;}
for (i=M;i<N;i++)
{
hB=nextHash(hB,B[i-M],B[i]);
if (hA==hB){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;
}