Pagini recente » Cod sursa (job #2425476) | Cod sursa (job #2895592) | Cod sursa (job #2034676) | Cod sursa (job #2023138) | Cod sursa (job #1550152)
#include <cstdio>
#include <cstring>
int m,n,p=73,p1,p2,i,a1,b1,a2,b2,MOD1=100007,MOD2=100021;
long long d;
char match[2000001],A[2000001],B[2000001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&A,&B);
m=strlen(A);
n=strlen(B);
p1=p2=1;
a1=a2=0;
for (i=0; i<=m-1; i++)
{
a1=(a1*p+A[i])%MOD1;
a2=(a2*p+A[i])%MOD2;
b1=(b1*p+B[i])%MOD1;
b2=(b2*p+B[i])%MOD2;
if (i!=0)
p1=(p1*p)%MOD1,
p2=(p2*p)%MOD2;}
if (m>n)
{
printf("0\n");
return 0;
}
int Nr = 0;
if(b1==a1&&b2==a2)match[0]=1,Nr++;
for (int i = m; i < n; i++)
{
b1=((b1-(B[i-m]*p1)%MOD1+MOD1)*p+B[i])%MOD1;
b2=((b2-(B[i-m]*p2)%MOD2+MOD2)*p+B[i])%MOD2;
if (b1==a1&&b2==a2)
match[i-m+1]=1, Nr++;
}
printf("%d\n",Nr);
Nr = 0;
for(int i = 0; i < n && Nr < 1000; i++)
if(match[i]) Nr++, printf("%d ",i);
printf("\n");
return 0;
}