Cod sursa(job #1188768)

Utilizator MarianMMorosac George Marian MarianM Data 20 mai 2014 16:07:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <string>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string P;
vector<char> Prefix;
vector<int> Apare;

int main(){
	int i, j, lg, s; char x;

	fin >> P; fin.get(x);
	lg = P.size();
	Prefix.push_back(0);
	for (j = 0, i = 1; i < lg; i++){
		if (P[j] == P[i])	j++;
		else{
			while (j && P[j] != x) 
				j = Prefix[j];
		}
		Prefix.push_back(j);
	}

	j = 0; s = 0;
	while (!fin.eof()){
		fin.get(x);

		if	(P[j] == x)	 j++;
		else	while (j && P[j] != x) j = Prefix[j];

		if (j == P.size())	Apare.push_back(s), j = Prefix[j - 1];
		s++;
	}

	fout << Apare.size() << "\n";
	for (i = 0; i < Apare.size() && i < 1000; i++)	fout << Apare[i] + 1 - P.size() << ' ';

	return 0;
}