Pagini recente » Cod sursa (job #2567252) | Cod sursa (job #503352) | Cod sursa (job #2028454) | Cod sursa (job #1881724) | Cod sursa (job #491072)
Cod sursa(job #491072)
#include <stdio.h>
#include <string.h>
int b,i,p,t,ok[130],sol,key,nr,j,pow,v,w[1002],m;
char P[2000002],T[2000002];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(P,2000002,stdin);
fgets(T,2000002,stdin);
p=strlen(P)-1;
if(P[p]=='\n') p--;
t=strlen(T)-1;
if(T[t]=='\n') t--;
for(i='0';i<='z';i++) ok[i]=0;
b=0;
for(i=0;i<=t;i++)
if(ok[T[i]-'0']==0)
{
b++;
ok[T[i]-'0']=1;
}
m=29837;
sol=0;
key=0;
pow=1;
b++;
for(i=p;i>=0;i--)
{
key+=pow*(P[i]-'0');
key%=m;
pow*=b;
pow%=m;
}
nr=0;
pow=1;
for(i=p;i>0;i--)
{
nr+=pow*(T[i]-'0');
nr%=m;
pow*=b;
pow%=m;
}
nr+=pow*(T[0]-'0');
nr%=m;
v=0;
for(j=0;j<=p;j++)
if(T[j]!=P[j])
{
v=1;
break;
}
if(v==0)
{
sol++;
if(sol<=1000) w[sol]=0;
}
for(i=p+1;i<=t;i++)
{
nr-=pow*(T[i-p-1]-'0');
if(nr<0) nr+=m;
nr*=b;
nr+=T[i]-'0';
nr%=m;
if(nr==key)
{
v=0;
for(j=0;j<=p;j++)
if(T[j+i-p]!=P[j])
{
v=1;
break;
}
if(v==0)
{
sol++;
if(sol<=1000) w[sol]=i-p;
}
}
}
printf("%d\n",sol);
if(sol>1000) sol=1000;
for(i=1;i<sol;i++)
printf("%d ",w[i]);
if(sol!=0) printf("%d\n",w[sol]);
return 0;
}