Pagini recente » Cod sursa (job #716777) | Cod sursa (job #969453) | Cod sursa (job #2168054) | Cod sursa (job #2450539) | Cod sursa (job #1671812)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD=666013, b=80, Max=2000005;
int rez[1005], hashA, hashB, nr;
char A[Max], B[Max];
int main()
{
fin>>A>>B;
int na=strlen(A);
int nb=strlen(B);
if(na>nb)
{
fout<<0;
return 0;
}
int p=1;
for(int i=0;i<na;i++)
{
int c=A[i]-'0'+1;
hashA=((hashA*b)%MOD+c)%MOD;
if(i!=0)
{
p*=b;
p%=MOD;
}
}
for(int i=0;i<na;i++)
{
int c=B[i]-'0'+1;
hashB=((hashB*b)%MOD+c)%MOD;
}
if(hashA==hashB)
{
nr++;
rez[nr]=0;
}
for(int i=na;i<nb;i++)
{
int c1=B[i-na]-'0'+1;
int c2=B[i]-'0'+1;
hashB=((hashB-(p*c1)%MOD+MOD)*b+c2)%MOD;
if(hashA==hashB)
{
int j;
for(j=0;j<na;j++)
{
if(A[j]!=B[i-na+1+j])
{
break;
}
}
if(j>=na)
{
nr++;
if(nr<=1000)
rez[nr]=i-na+1;
}
}
}
fout<<nr<<'\n';
for(int i=1;i<=min(nr,1000);i++)
{
fout<<rez[i]<<" ";
}
return 0;
}