Pagini recente » Cod sursa (job #1154722) | Cod sursa (job #1648416) | Cod sursa (job #2618396) | Cod sursa (job #2829687) | Cod sursa (job #2084423)
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000010],b[2000010];
int pbase=32771,match[1010];
int main()
{
FILE *f=fopen("strmatch.in","r");
fgets(a,2000010,f);
fgets(b,2000010,f);
int n=strlen(a),m=strlen(b);
if(a[n-1]=='\n')a[--n]=0;
if(b[m-1]=='\n')b[--m]=0;
int i,ha=0,hb=0,p256=1;
for(i=0;a[i];++i)
{
p256=p256*256%pbase;
ha=(ha*256+a[i])%pbase;
hb=(hb*256+b[i])%pbase;
}
int ok,j,nrap=0;
for(i=0;i<=m-n;++i)
{
if(ha==hb)
{
ok=1;
for(j=0;j<n;++j)
if(a[j]!=b[i+j]){ok=0;break;}
if(ok)
{
nrap++;
if(nrap<=1000)match[nrap]=i;
}
}
hb=((hb*256-b[i]*p256+b[i+n])%pbase+pbase)%pbase;
}
f=fopen("strmatch.out","w");
fprintf(f,"%d\n",nrap);
if(nrap>1000)nrap=1000;
for(i=1;i<=nrap;++i)fprintf(f,"%d ",match[i]);
return 0;
}