Pagini recente » Cod sursa (job #2302822) | Cod sursa (job #9408) | Cod sursa (job #2540311) | Cod sursa (job #1599930) | Cod sursa (job #820212)
Cod sursa(job #820212)
#include<cstdio>
#include<string.h>
#define p 73
#define mod1 100007
#define mod2 100021
#define maxn 2000010
char s[maxn],t[maxn];
int m[maxn],ct;
int hs1,hs2,ht1,ht2,p1,p2,i,ns,nt;
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&s,&t);
ns=strlen(s);
nt=strlen(t);
}
void first_word_hash()
{
p1=p2=1;
for(i=0;i<ns;i++)
{
hs1=(hs1*p+s[i])%mod1;
hs2=(hs2*p+s[i])%mod2;
if(i!=0)
{
p1=(p*p1)%mod1;
p2=(p*p2)%mod2;
}
}
}
int main()
{
citire();
first_word_hash();
if(strlen(s)>strlen(t))
{
printf("\n");
return 0;
}
for(i=0;i<ns;i++)
{
ht1=(ht1*p+t[i])%mod1;
ht2=(ht2*p+t[i])%mod2;
}
if(ht1==hs1&&ht2==hs2)
{
m[0]=1; ct++;
}
for(i=ns;i<nt;i++)
{
ht1=((ht1-(t[i-ns]*p1)%mod1+mod1)*p+t[i])%mod1;
ht2=((ht2-(t[i-ns]*p2)%mod2+mod2)*p+t[i])%mod2;
if(ht1==hs1&&ht2==hs2)
{
m[i-ns+1]=1; ct++;
}
}
printf("%d\n",ct);
ct=0;
for(i=0;i<nt&&ct<1000;i++)
{
if(m[i]==1) {ct++; printf("%d ",i);}
}
return 0;
}