Pagini recente » Cod sursa (job #240518) | Cod sursa (job #768955) | Cod sursa (job #580515) | Cod sursa (job #2539022) | Cod sursa (job #2541522)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000001], b[2000001];
int v[2000001];
int main() {
FILE *fin, *fout;
int n, m, x1, x2, y1, y2, nr, i, mod1=666013, mod2=1000003, p1, p2;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
fscanf(fin, "%s\n%s",&a,&b);
n=strlen(a);
m=strlen(b);
if(n>m) {
fprintf(fout, "0");
return 0;
}
x1=x2=y1=y2=0;
nr=1;
p1=p2=1;
for(i=0;i<n;i++) {
x1=(x1*74+a[i]-'0'+1)%mod1;
x2=(x2*74+a[i]-'0'+1)%mod2;
y1=(y1*74+b[i]-'0'+1)%mod1;
y2=(y2*74+b[i]-'0'+1)%mod2;
if(i!=0) {
p1=(p1*74)%mod1;
p2=(p2*74)%mod2;
}
}
if(x1==y1 && x2==y2)
v[nr++]=i-n+1;
for(i=n;i<m;i++) {
y1=((y1-(b[i-n]-'0'+1)*p1%mod1+mod1)*74+b[i]-'0'+1)%mod1;
y2=((y2-(b[i-n]-'0'+1)*p1%mod2+mod2)*74+b[i]-'0'+1)%mod2;
if(x1==y1 && x2==y2)
v[nr++]=i-n+1;
}
fprintf(fout, "%d\n",nr-1);
for(i=1;i<nr && i<=1000;i++)
fprintf(fout, "%d ",v[i]);
fclose( fin );
fclose( fout );
return 0;
}