Cod sursa(job #1598099)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 12 februarie 2016 16:58:31
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 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 = 0;
	int j = 0;
	int k = 0;
	while (i < pat.size())
	{
		j = 0;
		k = 0;
		while ((j <= i - j && j != 0) || j < i-j)
		{
			if (pat[j] == pat[i-j]) 
				++k;
			else 
				break;
			++j;
		}
		result.push_back(k);
		++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 (pat[j] == text[i]) {
			j++;
			i++;
		}
		if (j == pat.size()){
			Nr++;
			aparitii.push_back(i-j);
			j = result[j-1];
		}
		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);
	if (Nr != 0)
		fout<<Nr<<endl;
	while (!aparitii.empty()){
		int aux = aparitii.front();
		aparitii.erase(aparitii.begin());
		fout<<aux<<" ";
	}
	return 0;
}