#include <iostream>
#include <fstream>
#include <string>
#include <list>
using namespace std;

//#include "../utils/PerformanceTimer.h"

//int e_005_strmatch_()
int main()
{
	//PerformanceTimer timer;
	//timer.init();

	string in_file = "strmatch.in";
	string out_file = "strmatch.out";
	
	const int enought_matches = 1000;
		
	string us, vs;
	const char *u, *v;
	
	ifstream ifs(in_file.c_str());
	//ifs>>us>>vs;
	getline(ifs, us);
	getline(ifs, vs);
	ifs.close();

	//transfer us to u in order to speed up the accessing
	u = us.c_str();
	v = vs.c_str();

	list<int> complete_matches;

	int* T;
	if (us.size() <= vs.size())
	{
		//build the T table of the first string
		T = new int[us.size() + 1];
		T[0] = -1;
		T[us.size()] = 0;//this value can be modified below
		int j = 1;
		while (j < us.size())
		{
			int k = 0; 			
			while (j < us.size() && u[k] == u[j])
			{
				T[j] = k;
				k++;
				j++;
			}
			//the character after the match:
			//if (j < us.size()) T[j] = k;
			T[j] = k;//how many positions to return in case of mismatch;
			//also covers the case of success (when j == us.size())
			
			j++;			
		}
	}

	//processing
	int m = 0;
	int i = 0;
	while (m + i < vs.size())
	{		
		if (v[m + i] == u[i])
			if (i == us.size() - 1) 
			{
				complete_matches.push_back(m);				
				m = m + i - T[i];//i+1 is the first non-matching position, but produces the same m as i, T[i] (only in the case of a complete match)
				if (T[i] > -1) i = T[i];
				else i = 0;				
			}
			else i++;
		else
		{
			m = m + i - T[i];
			if (T[i] > -1) i = T[i];
			else i = 0;
		}
	}

	ofstream ofs(out_file.c_str());
	ofs<<complete_matches.size()<<"\n";
	int how_many_matches;
	list<int>::iterator it;
	for (it = complete_matches.begin(), how_many_matches = 1;
		it != complete_matches.end() && how_many_matches <= enought_matches; 
		it++, how_many_matches++)
		ofs<<*it<<" ";
	ofs.close();

	//release the memory
	delete[] T;
	
	//cout<<timer.getElapsedTime()<<endl;

	return 0;
}