Cod sursa(job #1188634)

Utilizator MarianMMorosac George Marian MarianM Data 20 mai 2014 02:19:20
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 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]){
			if (P[i] == P[i - 1])	j = Prefix[i - 1];
			else					j = Prefix[i - 1] + 1;
		}
		else						j = 0;
		Prefix.push_back(j);
	}

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

		if (P[j] == x)		j++;
		else if (j == 0)	j = 0;
		else				j = Prefix[j - 1];

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

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

	return 0;
}