Cod sursa(job #1201928)

Utilizator vasile_pojogaPojoga Vasile vasile_pojoga Data 26 iunie 2014 14:12:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string P,T;
int URM[2000005];
vector<int> result;
int nrSol;

void prefix();
void match();
void print();

int main()
{	
	fin>>P>>T;
	P = '#' + P;
	prefix();
	match();
	print();
	return 0;
}

void prefix()
{
	URM[1] = 0;
	int k = 0;
	for(int q=2; q<P.length(); q++)
	{
		while(k > 0 && P[k + 1] != P[q])
		{
			k = URM[k];
		}
		if(P[k + 1] == P[q])
		{
			k = k + 1;
		}
		URM[q] = k;
	}
}

void match()
{
	int q = 0;
	int m = P.length() - 1;
	nrSol = 0;
	for(int i=0;i<T.length();i++)
	{
		while(q > 0 && P[q + 1] != T[i])
		{
			q = URM[q];
		}
		if(P[q + 1] == T[i])
		{
			q = q + 1;
		}
		if(q == m)
		{
			++nrSol;
			if(nrSol<=1000)
			{
				result.push_back(i - m + 1);
			}					
		}
	}
}

void print()
{
	fout<<nrSol<<'\n';
	for(int i=0;i<result.size();i++)
	{
		fout<<result[i]<<' ';
	}
}