Pagini recente » Cod sursa (job #1681909) | Cod sursa (job #2056409) | Cod sursa (job #2677945) | Cod sursa (job #520906) | Cod sursa (job #1532862)
#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+s1[i])%100057;
h12=(h12*67+s1[i])%100043;
h21=(h21*67+s2[i])%100057;
h22=(h22*67+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]);
}
}
}