Pagini recente » Cod sursa (job #1351391) | Cod sursa (job #2852247) | Cod sursa (job #1167977) | Cod sursa (job #1314784) | Cod sursa (job #1402374)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define nmax 2000001
#define mod1 100009
#define mod2 100079
#define p 57
using namespace std;
FILE *f=fopen("strmatch.in","r"),*g=fopen("strmatch.out","w");
int ha1,ha2,h1,h2,k,r[1001];
char a[nmax],b[nmax];
int main()
{
int i,j,la,lb,p1=1,p2=1;
fscanf(f,"%s %s",a,b);
la=strlen(a);
lb=strlen(b);
for(i=0;i<la;i++)
{
ha1=(ha1*p+a[i])%mod1;
ha2=(ha2*p+a[i])%mod2;
if(i!=0)
p1=(p1*p)%mod1,
p2=(p2*p)%mod2;
}
for(i=0;i<la;i++)
{
h1=(h1*p+b[i])%mod1;
h2=(h2*p+b[i])%mod2;
}
if(h1==ha1&&h2==ha2)
r[++k]=0;
for(i=la;i<lb;i++)
{
h1=((h1-(b[i-la]*p1)%mod1+mod1)*p+b[i])%mod1;
h2=((h2-(b[i-la]*p2)%mod2+mod2)*p+b[i])%mod2;
if(h1==ha1&&h2==ha2)
{
k++;
if(k<=1000)
r[k]=i-la+1;
}
}
fprintf(g,"%d\n",k);
for(i=1;i<=min(k,1000);i++)
fprintf(g,"%d ",r[i]);
fclose(f);
fclose(g);
return 0;
}