Pagini recente » Cod sursa (job #153991) | Cod sursa (job #2116645) | Cod sursa (job #2945595) | Cod sursa (job #697763) | Cod sursa (job #2065288)
#include <fstream>
#include <string.h>
#define mod1 100007
#define mod2 100003
using namespace std;
int hash1,hash2,hash3,hash4,lg1,lg2,i,nr,v[1001],k;
char a[2000001],b[2000001];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
f>>a>>b;
lg1=strlen(a);
lg2=strlen(b);
if(lg1>lg2) g<<0;
else{
for(i=0;i<lg1;i++)
{
hash1=(hash1+a[i])%mod1;
hash2=(hash2+a[i])%mod2;
hash3=(hash3+b[i])%mod1;
hash4=(hash4+b[i])%mod2;
}
if(hash1==hash3&&hash2==hash4)
nr++,v[++k]=1;
for(i=lg1;i<lg2;i++)
{
hash3=hash3+b[i]-b[i-lg1];
if(hash3<0) hash3+=mod1;
else hash3=hash3%mod1;
hash4=hash4+b[i]-b[i-lg1];
if(hash3<0) hash4+=mod2;
else hash4=hash4%mod2;
if(hash3==hash1&&hash4==hash2)
{nr++;
if(k<1000) v[++k]=i-lg1+1;}
}
g<<nr<<'\n';
for(i=1;i<=k;i++) g<<v[i]<<' ';
}
return 0;
}