Pagini recente » Cod sursa (job #1562684) | Cod sursa (job #1301372) | Cod sursa (job #324432) | Cod sursa (job #1993790) | Cod sursa (job #1532858)
#include<stdio.h>
#include<string.h>
FILE *fin,*fout;
char s1[2000002],s2[2000002];
int l1,l2;
int res[2000002],pos;
long long int h11,h12,h21,h22;
long long int v1,v2;
int main()
{
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
fscanf(fin,"%s",s1+1);
l1=strlen(s1+1);
fscanf(fin,"%s",s2+1);
l2=strlen(s2+1);
v1=1;
v2=1;
for(int i=1;i<=l1;i++)
{
h11=((h11*67)%100057+s1[i])%100057;
h12=((h12*67)%100043+s1[i])%100043;
h21=((h21*67)%100057+s2[i])%100057;
h22=((h22*67)%100043+s2[i])%100043;
if(i!=1)
{
v1*=67;
v1%=100057;
v2*=67;
v2%=100043;
}
}
//fprintf(fout,"%lld %lld %lld %lld\n",h11,h12,h21,h22);
if(h11==h21&&h12==h22)
{
pos++;
res[pos]=0;
}
for(int i=l1+1;i<=l2;i++)
{
h21=((h21-(v1*s2[i-l1])%100057+100057)*67+s2[i])%100057;
h22=((h22-(v2*s2[i-l1])%100043+100043)*67+s2[i])%100043;
if(h11==h21&&h12==h22)
{
pos++;
res[pos]=i-l1;
}
//fprintf(fout,"%lld %lld %lld %lld\n",h11,h12,h21,h22);
}
fprintf(fout,"%d\n",pos);
if(pos<=1000)
{
for(int i=1;i<=pos;i++)
{
fprintf(fout,"%d ",res[i]);
}
}
else
{
for(int i=1;i<=1000;i++)
{
fprintf(fout,"%d ",res[i]);
}
}
}