Pagini recente » Cod sursa (job #301641) | Cod sursa (job #2803123) | Cod sursa (job #1125398) | Cod sursa (job #1778427) | Cod sursa (job #2539397)
#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*27+a[i]-'A'+1)%mod1;
x2=(x2*27+a[i]-'A'+1)%mod2;
y1=(y1*27+b[i]-'A'+1)%mod1;
y2=(y2*27+b[i]-'A'+1)%mod2;
if(i!=0) {
p1=(p1*27)%mod1;
p2=(p2*27)%mod2;
}
}
if(x1==y1 && x2==y2)
v[nr++]=i-n+1;
for(i=n;i<m;i++) {
y1=((y1%p1)*27+b[i]-'A'+1)%mod1;
y2=((y2%p2)*27+b[i]-'A'+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;
}