Pagini recente » Cod sursa (job #1405051) | Cod sursa (job #630417) | Cod sursa (job #261535) | Cod sursa (job #431831) | Cod sursa (job #2189447)
#include <cstdio>
#define H1 100000007
#define H2 100000037
#define MAXR 1000
#define MAXN 2000000
typedef struct{
int v1, v2;
}val;
val r;
int rez[MAXR], dr;
char a[MAXN + 2], b[MAXN + 2];
inline void update(val &x, int y){
x.v1 = (x.v1 * 10 + y) % H1;
x.v2 = (x.v2 * 10 + y) % H2;
}
inline void update2(val &x, int y){
x.v1 = (x.v1 - 1LL * r.v1 * y) % H1;
if(x.v1 < 0)
x.v1 += H1;
x.v2 = (x.v2 - 1LL * r.v2 * y) % H2;
if(x.v2 < 0)
x.v2 += H2;
}
int main(){
FILE *in = fopen("strmatch.in", "r");
int n, m, i;
fgets(a, MAXN + 2, in);
fgets(b, MAXN + 2, in);
fclose(in);
n = m = 0;
while(a[n] != '\n')
n++;
while(b[m] != '\n')
m++;
r.v1 = r.v2 = 1;
for(i = 0; i < n; i++){
r.v1 = 10 * r.v1 % H1;
r.v2 = 10 * r.v2 % H2;
}
val va, vb;
va.v1 = va.v2 = vb.v1 = vb.v2 = 0;
for(i = 0; i < n; i++){
update(va, a[i]);
update(vb, b[i]);
}
do{
if(va.v1 == vb.v1 && va.v2 == vb.v2){
if(dr < MAXR)
rez[dr] = i;
dr++;
}
update(vb, b[i]);
update2(vb, b[i - n]);
i++;
}while(i < m);
FILE *out = fopen("strmatch.out", "w");
fprintf(out, "%d\n", dr);
for(i = 0; i < dr && i < MAXR; i++)
fprintf(out, "%d ", rez[i] - n);
fclose(out);
return 0;
}