Pagini recente » Cod sursa (job #3157881) | Cod sursa (job #1656708) | Cod sursa (job #1127731) | Borderou de evaluare (job #1569197) | Cod sursa (job #415146)
Cod sursa(job #415146)
#include<stdio.h>
#include<string.h>
#define min(a,b) a < b ? a : b
#define MAX 2000001
#define p 73
#define m1 100007
#define m2 100021
char s1[MAX],s2[MAX];
int n1,n2,p1=1,p2=1,h1s1,h1s2,h2s1,h2s2,i,sol[MAX],k,t;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&s1,&s2);
n1=strlen(s1);
n2=strlen(s2);
for(i=0;i<n1;i++)
{
h1s1=(h1s1*p+s1[i])%m1;
h2s1=(h2s1*p+s1[i])%m2;
if(i)
{
p1=(p1*p)%m1;
p2=(p2*p)%m2;
}
}
for(i=0;i<n2;i++)
{
if(i<n1)
{
h1s2=(h1s2*p+s2[i])%m1;
h2s2=(h2s2*p+s2[i])%m2;
}
else
{
h1s2=((h1s2-(s2[i-n1]*p1)%m1+m1)*p+s2[i])%m1;
h2s2=((h2s2-(s2[i-n1]*p2)%m2+m2)*p+s2[i])%m2;
}
if(h1s1==h1s2&&h2s1==h2s2)
{
sol[k]=i-n1+1;
k++;
}
}
printf("%d\n",k);
t=min(k,1000);
for(i=0;i<t;i++)
printf("%d ",sol[i]);
return 0;
}