Cod sursa(job #499736)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 10 noiembrie 2010 18:58:47
Problema Potrivirea sirurilor Scor 66
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void calc_prefix(string a, vector<int> &prefix) {
	int i, pos = 0;
	prefix[1] = 0;
	for (i = 2; i < a.size(); ++i)
	{
		while (pos && a[pos+1] != a[i])
		pos = prefix[pos];
		if (a[pos+1] == a[i])
		++pos;
		prefix[i] = pos;
	}
}
void find_matches(string a, string b, vector <int> prefix, vector<int>& matches) {
	int pos = 0;
	for (int i = 1; i < b.size(); ++i)
	{      
		while (pos && a[pos+1] != b[i])
		pos = prefix[pos];
		if (a[pos+1] == b[i])
			++pos;
		if (pos == a.size() - 1)
		{
			pos = prefix[a.size() - 1];
			matches.push_back(i - a.size() + 1);
		}
	} 
}

int main() {
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	string a, b;
	fin >> a;
	fin >> b;
	a = '3' + a;
	b = '3' + b;
	if (a.size() > b.size()) {
		fout << 0 << endl;
	}
	vector<int> prefix(a.size() + 1);
	calc_prefix(a, prefix);
	vector<int> matches;
	find_matches(a, b, prefix, matches);
	fout << matches.size() << endl;
	for (int i = 0; i < matches.size(); i++) {
		if (i < 1000)
			fout << matches[i] << " ";
	}
	fout << endl;
	fout.close();
	return 0;
}