Pagini recente » Cod sursa (job #830126) | Cod sursa (job #1555709) | Cod sursa (job #1916770) | Cod sursa (job #61000) | Cod sursa (job #496641)
Cod sursa(job #496641)
#include <stdio.h>
#include <string.h>
long M,B,cod,sir,n,m,i,pow,sol,v[1002],ok[255];
char a[2000002],b[2000002];
long ver(long x)
{
long i;
for(i=x;i<=x+n;i++)
if(a[i-x]!=b[i]) return 0;
return 1;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,2000002,stdin);
fgets(b,2000002,stdin);
n=strlen(a)-1;
if(a[n]=='\n') n--;
m=strlen(b)-1;
if(b[m]=='\n') m--;
sir=0;
cod=0;
B=0;
M=999983;
for(i=0;i<=n;i++)
{
if(ok[a[i]]==0)
ok[a[i]]=++B;
a[i]=ok[a[i]];
}
for(i=0;i<=m;i++)
{
if(ok[b[i]]==0)
ok[b[i]]=++B;
b[i]=ok[b[i]];
}
pow=1;
for(i=n;i>=0;i--)
{
sir+=a[i]*pow;
sir%=M;
pow*=B;
pow%=M;
}
pow=1;
for(i=n;i>=0;i--)
{
cod+=b[i]*pow;
cod%=M;
pow*=B;
pow%=M;
}
sol=0;
if(cod==sir)
if(ver(0))
{
sol++;
if(sol<=1000) v[sol]=0;
}
for(i=n+1;i<=m;i++)
{
cod*=B;
cod-=pow*b[i-n-1];
if(cod<0) cod+=M;
cod+=b[i];
cod%=M;
if(cod==sir)
if(ver(i-n))
{
sol++;
if(sol<=1000) v[sol]=i-n;
}
}
printf("%ld\n",sol);
if(sol>1000) sol=1000;
for(i=1;i<=sol;i++)
printf("%ld ",v[i]);
printf("\n");
return 0;
}