Pagini recente » Cod sursa (job #1243715) | Cod sursa (job #307581) | Cod sursa (job #1370936) | Cod sursa (job #1430071) | Cod sursa (job #292321)
Cod sursa(job #292321)
#include<fstream.h>
#include<string.h>
#define mod1 100003
#define mod2 100019
#define BASE 61
char a[mod1+1],b[mod2+1];
int hash1,hash2,p1,p2;
char pos[mod2+1];
int main()
{
ifstream be ("strmatch.in");
ofstream ki ("strmatch.out");
be>>a>>b;
int i,n,m,hash1,hashh1,hash2,hashh2,p1,p2,nr=0;
be.close();
n=strlen(a);
m=strlen(b);
hash1=hash2=hashh1=hashh2=0;
p1=p2=1;
for (i=0;i<n;++i)
{
hash1=(hash1*BASE+a[i])%mod1;
hash2=(hash2*BASE+a[i])%mod2;
if (i)
p1=(p1*BASE)%mod1,p2=(p2*BASE)%mod2;
}
for (i=0;i<n;++i)
{
hashh1=(hashh1*BASE+b[i])%mod1;
hashh2=(hashh2*BASE+b[i])%mod2;
}
if (hash1==hashh1 && hash2==hashh2)
pos[0]=1,nr++;
for (i=n;i<m;++i)
{
hashh1=(hashh1-b[i-n]*p1)%mod1;
hashh2=(hashh2-b[i-n]*p2)%mod2;
hashh1=(hashh1+b[i]*BASE)%mod1;
hashh2=(hashh2+b[i]*BASE)%mod2;
if (hash1==hashh1 && hash2==hashh2)
pos[i-n+1]=1,nr++;
}
ki<<nr<<'\n';
nr=0;
for (i=1;i<m && nr<1000;++i)
if (pos[i])
ki<<i<<'\n',++nr;
ki.close();
return 0;
}