// Mihai Priboi
#include <bits/stdc++.h>
#define HASHSIZE1 1000003
#define HASHSIZE2 666013
#define HASHBASE1 511
#define HASHBASE2 255
#define MAXLEN 2000002
#define MAXRASP 1000
char v[MAXLEN];
int rasp[MAXRASP];
int getHash( int first, int size, int hashbase, int hashsize ) {
int rez, i;
rez = 0;
for( i = first; i < first + size; i++ )
rez = ( rez * hashbase + v[i] ) % hashsize;
return rez;
}
void shiftHash( int &hash, char ch1, char ch2, int hashbase, int hashbasepow, int hashsize ) {
// stergem primul element
hash -= ch1 * hashbasepow % hashsize;
hash += hash < 0 ? hashsize : 0;
// adaugam un element la final
hash = ( hash * hashbase + ch2 ) % hashsize;
}
int main() {
FILE *fin, *fout;
char ch;
int na, nb, hash1, hash2, hashbasepow1, hashbasepow2, a_hash1, a_hash2, cnt, i;
fin = fopen( "strmatch.in", "r" );
fgets( v, MAXLEN, fin );
na = strlen(v) - 1;
a_hash1 = getHash( 0, na, HASHBASE1, HASHSIZE1 );
a_hash2 = getHash( 0, na, HASHBASE2, HASHSIZE2 );
fgets( v, MAXLEN, fin );
nb = strlen(v) - 1;
fclose( fin );
hash1 = getHash( 0, na, HASHBASE1, HASHSIZE1 );
hash2 = getHash( 0, na, HASHBASE2, HASHSIZE2 );
hashbasepow1 = hashbasepow2 = 1;
for( i = 1; i < na; i++ ) {
hashbasepow1 = hashbasepow1 * HASHBASE1 % HASHSIZE1;
hashbasepow2 = hashbasepow2 * HASHBASE2 % HASHSIZE2;
}
cnt = 0;
for( i = 0; i < nb - na + 1; i++ ) {
if( i > 0 ) {
shiftHash( hash1, v[i - 1], v[i + na - 1], HASHBASE1, hashbasepow1, HASHSIZE1 );
shiftHash( hash2, v[i - 1], v[i + na - 1], HASHBASE2, hashbasepow2, HASHSIZE2 );
}
if( hash1 == a_hash1 && hash2 == a_hash2 ) {
if( cnt < MAXRASP )
rasp[cnt] = i;
cnt++;
}
}
fout = fopen( "strmatch.out", "w" );
fprintf( fout, "%d\n", cnt );
for( i = 0; i < std::min( cnt, MAXRASP ); i++ )
fprintf( fout, "%d ", rasp[i] );
fclose( fout );
return 0;
}