#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#define HASH_BASE 101
#define MAXS 2000001

int init_hash(char* low, char* up) {
	int hash = 0;
	int base = 1;

	while(up > low) {
		up--;
		hash += base * (*up);
		base *= HASH_BASE;
	}
	
	return hash;
}

int roll_hash(int oldv, int hash, int newv, int exp) {
    hash -= oldv*pow(HASH_BASE, exp-1);
    hash *= HASH_BASE;
    hash += newv;
    return hash;
}

int main() {
	char *a;
	char *b, *c;
	int M, N, nr_matches = 0, poz[1000];
	int a_hash, sub_hash;
	int i, max;
	FILE *f;

	f = fopen("strmatch.in","rt");
	a = malloc(MAXS*sizeof(char));
	b = malloc(MAXS*sizeof(char));
	fgets(a,  MAXS, f);
	fgets(b,  MAXS, f);
	fclose(f);
	c = strdup(a);
	
	M = strlen(a);
	N = strlen(b);
	a_hash = init_hash(a,a+M);
	sub_hash = init_hash(b,b+M);

	for(i = 0; i < N-M+1; i++) {
		if(a_hash == sub_hash) {
			strncpy(c, b+i, M);
			if(strcmp(a, c) == 0) {
				nr_matches++;
				if(nr_matches <= 1000)
					poz[nr_matches-1] = i;
			}
		}
		sub_hash = roll_hash(b[i], sub_hash, b[i+M], M);
	}

	free(a);
	free(b);
	free(c);
	f = fopen("strmatch.out", "wt");
	fprintf(f,"%i\n",nr_matches);
	max = 1000 < nr_matches? 1000: nr_matches;
	for(i = 0; i < max; i++)
		fprintf(f,"%i ",poz[i]);
	fclose(f);
}