#include <fstream>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

const char NUME_FISIER_INTRARE[] = "strmatch.in";
const char NUME_FISIER_IESIRE[] = "strmatch.out";
const int MAX_NR_POZITII = 1000;
const int MARIME_ALFABET = 256;

struct DateIesire{
	int n;
	vector<int> *pozitii;

	void aloca(){
		n = 0;
		pozitii = new vector<int>(MAX_NR_POZITII);
	}

	void sterge(){
		delete pozitii;
	}

	void adaugaSolutie(int pozitie){
		if(n < 1000){
			(*pozitii)[n] = pozitie;
		}
		++n;
	}
};


class Matrice{
private:
	int n, m;
	int **matrice;
public:
	Matrice(int n, int m){
		this->n = n;
		this->m = m;
		this->matrice = creeazaMatrice(this->n, this->m);
	}
	~Matrice(){
		for(int i = 0; i < n; ++i){
			delete[] matrice[i];
		}
		delete[] matrice;
	}

	int* operator[](int i){
		return matrice[i];
	}
private:
	int **creeazaMatrice(int n, int m){
		int **matrice = new int* [n];
		for(int i = 0; i < n; ++i){
			matrice[i] = new int [m];
		}

		return matrice;
	}
};


class KMPAutomaton{
private: 
	int marime_alfabet;
	Matrice *matrice_stari;
	string tipar;

public: 
	KMPAutomaton(string str1, int marime_alfabet){
		
		this->tipar = str1;
		this->marime_alfabet = marime_alfabet;
		matrice_stari = new Matrice(tipar.size()+1, marime_alfabet);
		construiesteMatriceStari();
	}

	~KMPAutomaton(){
		delete matrice_stari;
	}

	DateIesire cautaSubstring(ifstream &fin){
		int j = 0, c_count = 0;
		char c;
		DateIesire date_iesire;
		date_iesire.aloca();
		while(!fin.eof()){
			fin >> c;
			j = (*matrice_stari)[j][c];

			if(j == tipar.size()){
				date_iesire.adaugaSolutie(c_count - tipar.size() + 1);
				j = (*matrice_stari)[j][c];
			}
			++c_count;
		}

		return date_iesire;

	}

	void debugDFA(){
		for(int i = 0; i <= tipar.size(); ++i){
			for(int j = 0; j < marime_alfabet; ++j){
				cout << (*matrice_stari)[i][j] << " ";
			}
			cout << "\n";
		}
	}

private: 
	void construiesteMatriceStari(){
		int X = 0; //starea de unde se continua
		for(int c = 0; c < marime_alfabet; ++c){
			(*matrice_stari)[X][c] = 0;
		}
		(*matrice_stari)[X][tipar[0]] = 1;

		for(int j = 1; j < tipar.size(); ++j){
			for(int c = 0; c < marime_alfabet; ++c){
				(*matrice_stari)[j][c] = (*matrice_stari)[X][c];
			}

			(*matrice_stari)[j][tipar[j]] = j+1;
			X = (*matrice_stari)[X][tipar[j]];
		}

		for(int c = 0; c < marime_alfabet; ++c){
			(*matrice_stari)[tipar.size()][c] = (*matrice_stari)[X][c];
		}
	}

};

void afiseazaDate(const char filename[], DateIesire date_iesire){
	//afiseaza numarul de potriviri si vectorul cu pozitia fiecareia
	ofstream fout(filename);
	fout << date_iesire.n << "\n";
	for(int i = 0; i < date_iesire.n && i < MAX_NR_POZITII; ++i){
		fout << (*date_iesire.pozitii)[i] << " ";
	}
	
	fout.close();
}

int main(int argc, char *argv[]){
	string str1;
	DateIesire date_iesire;
	ifstream fin(NUME_FISIER_INTRARE);

	fin >> str1;
	KMPAutomaton *kmp_automaton = new KMPAutomaton(str1, MARIME_ALFABET);
	date_iesire = kmp_automaton->cautaSubstring(fin);

	afiseazaDate(NUME_FISIER_IESIRE, date_iesire);

	delete kmp_automaton;
	date_iesire.sterge();

	return 0;
}