Cod sursa(job #1596631)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 11 februarie 2016 11:16:17
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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 (text[i] == pat[j] && j == pat.size() - 1)
		{
			//cout<<i-j;
			Nr++;
			aparitii.push_back(i-j);
			i = i - j;
			i = i + j - result[j-1];
			j = 0;
			continue;
		}
		else if (text[i] == pat[j])
		{
			j++;
		}
		else if (j != 0) {
			i = i - j;
			i = i + j - result[j-1];
			j = 0;
			continue;
		}
		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;
}