#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;
	
	if (us.size() <= vs.size())
	{
		//build the KMP T table of the first string
		int* T = new int[us.size()];
		T[0] = -1; T[1] = 0;

		int j = 2;
		int k = 0;
		while (j < us.size())
		{
			if (u[j-1] == u[k])
			{
				k++; T[j] = k; j++;
			}
			else if (k > 0) k = T[k];
			else T[j++] = 0;
		}								
	
		//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];
					if (T[i] > -1) i = T[i];
					else i = 0;
				}
				i++;
			}
			else
			{
				m = m + i - T[i];
				if (T[i] > -1) i = T[i];
				else i = 0;
			}
		}
		
		/*int m = 0; 
		int i = 0;
		while (m + i < vs.size())
		{
			//if (v[m + i] == u[i])
		}*/
	
		//release the memory
		delete[] T;
	}

	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();
	
	cout<<timer.getElapsedTime()<<endl;

	return 0;
}