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