Pagini recente » Cod sursa (job #565334) | Cod sursa (job #2937221) | Cod sursa (job #48942) | Cod sursa (job #3174185) | Cod sursa (job #496647)
Cod sursa(job #496647)
#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]];
}
for(i=0;i<=n;i++)
sir=(sir*B+a[i])%M;
for(i=0;i<=n;i++)
cod=(cod*B+b[i])%M;
pow=1;
for(i=0;i<n;i++)
pow=(pow*B)%M;
sol=0;
if(cod==sir)
if(ver(0))
{
sol++;
if(sol<=1000) v[sol]=0;
}
for(i=n+1;i<=m;i++)
{
cod=(cod+M-(b[i-n-1]*pow)%M)%M;
cod=(cod*B+b[i])%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;
}