Cod sursa(job #1606589)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 20 februarie 2016 13:25:53
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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 == 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;
}