Cod sursa(job #1618719)

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

#define minim(a, b) ((a < b) ? a : b)

int pos[1024];
int n = 0;

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++;
			}
		}
	}
}

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++;
		}
	}
}

int main() {
	std::ifstream fin("strmatch.in");
	std::ofstream fout("strmatch.out");

	std::string pattern, text;

	fin >> pattern; fin >> text;
	std::vector<int> pi;
	built_match_table(pi, pattern);
	AlgKMP(pi, pattern, text);

	fout << n << '\n';
	for (int i = 0; i < minim(n, 1000); i++) {
		fout << pos[i] << " "; 
	}

	return 0;
}