Cod sursa(job #1618730)

Utilizator laurentiu.piciuPiciu Laurentiu laurentiu.piciu Data 27 februarie 2016 23:06:12
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

int pos[1024];
int n = 0;
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

void built_match_table(std::vector<int>& pi, std::string pattern) {
	int i = 1;
	int len = 0; /* lungimea celui mai lung prefix care este si sufix */
	pi.push_back(0);

	while (i < pattern.size()) {
		if (pattern[i] == pattern[len]) {
			len++;
			pi.push_back(len);
			i++;
		}
		else {
			if (len) {
				len = pi[len - 1];
			}
			else {
				pi.push_back(0);
				i++;
			}
		}
	}
}

int minim(int, int);

void AlgKMP (std::vector<int>& pi, std::string pattern, std::string text) {
	int i = 0, j = 0;
	while (i < text.size()) {
		if (text[i] == pattern[j]) {
			j++; i++;
		}
		
		if (j == pattern.size()) {
			pos[n] = i - j;
			n++;
			j = pi[j - 1];
		}
		else if (i < text.size() && pattern[j] != text[i]) {
			if (j != 0) 
				j = pi[j - 1];
			else
				i++;
		}
	}
	fout << n << '\n';
	if (n) {
		for (int i = 0; i < minim(n, 1000); i++) {
			fout << pos[i] << " ";
		}
		fout << '\n';
	}
}

int main() {
	std::string pattern, text;
	std::vector<int> pi;

	fin >> pattern; fin >> text;
	
	built_match_table(pi, pattern);
	AlgKMP(pi, pattern, text);

	return 0;
}

int minim(int a, int b) {
	return (a < b) ? a : b;
}