Pagini recente » Cod sursa (job #537139) | Cod sursa (job #795977) | Cod sursa (job #68725) | Cod sursa (job #710120) | Cod sursa (job #2084422)
#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%pbase-b[i]*p256+b[i+n])%pbase;
if(hb<0)hb+=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;
}