Cod sursa(job #1610211)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 23 februarie 2016 12:48:25
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout ("strmatch.out");
int Nr;
vector<int> aparitii;

void longestProperPrefix (vector<int>& result, string pat){
	int i = 1;
	int len = 0;
	result.push_back(0);
	//din nou
	while (i < pat.size())
	{
		if (pat[len] == pat[i]){
			++len;
			result.push_back(len);
			++i;
		}
		else {
			if (len != 0) {
				len = result[len-1];
			}
			else {
				result.push_back(0);
				++i;
			}
		}
	}
}
void KMP (vector<int>& result, string text, string pat){
	int i = 0, j = 0;
	while (i < text.size()) 
	{
		//cout<<text[i]<<" "<<j<<endl;
		if (text[i] == pat[j])
		{
			++j;
			++i;
		}
		if (j == pat.size())
		{
			j = result[j-1];
			Nr++;
			aparitii.push_back(i);
		}
		else if (i < text.size() && pat[j] != text[i]) {
			if (j != 0)
				j = result[j-1];
			else 
				i++;
		}
	}
}
int main(){
	string patt;
	string text;
	//fin.open("strmatch.in");
	//fin.open("strmatch.out");
	getline(fin,patt);
	getline(fin,text);
	vector<int> result;
	longestProperPrefix (result, patt);
	//for (int i = 0; i<result.size();++i)
	//			cout<<result[i]<<" ";
	KMP (result, text, patt);
	fout<<Nr<<endl;
	if (Nr != 0){
		while (!aparitii.empty()){
			int aux = aparitii.front();
			aparitii.erase(aparitii.begin());
			fout<<aux<<" ";
		}
	}
	return 0;
}