Pagini recente » Cod sursa (job #402373) | Cod sursa (job #929290) | Cod sursa (job #1354376) | Cod sursa (job #1757419) | Cod sursa (job #2208199)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,hashA1,hashA2,hashA3,P1,P2,P3,MOD1=100153,MOD2=100189,MOD3=100207,P=73,NA,NB,hashB1,hashB2,hashB3,nr;
char A[2000005],B[2000005],sol[2000005];
int main()
{
fin>>A;
fin>>B;
NA=strlen(A);
NB=strlen(B);
P1=1;P2=1;P3=1;
for(i=0;i<NA;i++)
{
hashA1=(hashA1*P+A[i])%MOD1;
hashA2=(hashA2*P+A[i])%MOD2;
hashA3=(hashA3*P+A[i])%MOD3;
if(i!=0)
{
P1=(P1*P)%MOD1;
P2=(P2*P)%MOD2;
P3=(P3*P)%MOD3;
}
}
if(NA>NB)
{
fout<<0<<"\n";
return 0;
}
for(i=0;i<NA;i++)
{
hashB1=(hashB1*P+B[i])%MOD1;
hashB2=(hashB2*P+B[i])%MOD2;
hashB3=(hashB3*P+B[i])%MOD3;
}
nr=0;
if(hashB1==hashA1 && hashB2==hashA2 && hashB3==hashA3)
{
sol[0]=1;
nr++;
}
for(i=NA;i<NB;i++)
{
hashB1=((hashB1-(B[i-NA]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
hashB2=((hashB2-(B[i-NA]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
hashB3=((hashB3-(B[i-NA]*P3)%MOD3+MOD3)*P+B[i])%MOD3;
if(hashB1==hashA1 && hashB2==hashA2 && hashB3==hashA3)
{
sol[i-NA+1]=1;
nr++;
}
}
fout<<nr<<"\n";
nr=0;
for(i=0;i<NB && nr<1000;i++)
{
if(sol[i]==1)
{
nr++;
fout<<i<<" ";
}
}
fin.close();
fout.close();
return 0;
}