Pagini recente » Cod sursa (job #2370599) | Cod sursa (job #908601) | Cod sursa (job #2735682) | Cod sursa (job #847278) | Cod sursa (job #1789419)
#include <cstdio>
#include <cstring>
char sir1[2000010],sir2[2000010];
const int mod1=666013,mod2=100007,baza=153;
int v[2000010];
using namespace std;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int l1,l2,p1,p2,hash1=0,hash2=0,hash11=0,hash22=0,sol=0;
scanf("%s\n%s",sir1,sir2);
l1=strlen(sir1);
l2=strlen(sir2);
p1=1;
p2=1;
for(int i=0;i<l1;i++)
{
hash1=(hash1*baza+sir1[i])%mod1;
hash2=(hash2*baza+sir1[i])%mod2;
if(i<l1-1)
{
p1=(p1*baza)%mod1;
p2=(p2*baza)%mod2;
}
}
if(l1>l2)
{
printf("0");
return 0;
}
for(int i=0;i<l1;i++)
{
hash11=(hash11*baza+sir2[i])%mod1;
hash22=(hash22*baza+sir2[i])%mod2;
}
if(hash1==hash11 && hash2==hash22)
{
sol++;
v[sol]=0;
}
for(int i=l1;i<l2;i++)
{
hash11=((hash11-(sir2[i-l1]*p1)%mod1)*baza+sir2[i])%mod1;
hash22=((hash22-(sir2[i-l1]*p2)%mod2)*baza+sir2[i])%mod2;
if(hash11==hash1 && hash22==hash2)
{
sol++;
v[sol]=i-l1+1;
}
}
printf("%d\n",sol);
for(int i=1;i<=sol;i++)
printf("%d ",v[i]);
return 0;
}