Cod sursa(job #2569228)

Utilizator gazdac_alex@yahoo.comGazdac Alexandru Eugen [email protected] Data 4 martie 2020 11:34:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

int const maxim = 2000005;

vector<int> stocare;


void compute_lps(string model, int dimensiune_model, int* lps) {
	
	int len = 0;
	lps[0] = 0;

	int i = 1;
	while (i < dimensiune_model) {
		if (model[i] == model[len]) {
			len++;
			lps[i] = len;
			i++;
		}
		else {
			if (len != 0) {
				len = lps[len - 1];
			}
			else {
				lps[i] = 0;
				i++;
			}
		}
	}
}


void kmp(string model, string sir) {
	
	int dimensiune_model = model.size();
	int dimensiune_sir = sir.size();

	int* lps= new int[dimensiune_model];

	compute_lps(model, dimensiune_model, lps);

	int index_model = 0;
	int index_sir = 0;
	while (index_sir < dimensiune_sir) {
		if (model[index_model] == sir[index_sir]) {
			index_model++;
			index_sir++;
		}
		if (index_model == dimensiune_model) {
			stocare.push_back(index_sir - index_model);
			index_model = lps[index_model - 1];
		}
		else if (index_sir < dimensiune_sir && model[index_model] != sir[index_sir]) {
			if (index_model == 0) {
				index_sir++;
			}
			else {
				index_model = lps[index_model - 1];
			}
		}
	}
}

void afisare() {
	out << stocare.size() << endl;
	if (stocare.size() <= 1000) {
		for (size_t i = 0; i < stocare.size(); i++) {
			out << stocare[i] << " ";
		}
	}
	else {
		for (size_t i = 0; i < 1000; i++) {
			out << stocare[i];
		}
	}
}



int main() {
	string model;
	string sir;
	
	in >> model;
	in >> sir;

	kmp(model, sir);
	afisare();
	return 0;
}