Cod sursa(job #964473)

Utilizator gabrieligabrieli gabrieli Data 21 iunie 2013 07:52:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
//BEGIN CUT
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

//END CUT
struct Kmp {
	string pattern;
	vector<int> prefix;

	void preprocess_pattern() {
		prefix.resize(pattern.size());

		int pos = -1;
		prefix[0] = -1;
		for (size_t i = 1; i < pattern.size(); ++i)
		{
			while (pos != -1 && pattern[pos+1] != pattern[i])
				pos = prefix[pos];
			if (pattern[pos+1] == pattern[i])
				pos += 1;
			prefix[i] = pos;
		}
	}

    vector<int> get_matches(const string &text) {
    	vector<int> matches;

    	int pos = -1;
    	for (size_t i = 0; i < text.size(); ++i)
		{
			while (pos != -1 && pattern[pos+1] != text[i])
				pos = prefix[pos];
			if (pattern[pos+1] == text[i])
				pos += 1;
			if (pos == pattern.size()-1)
			{
				matches.push_back(i - pattern.size() + 1);
				pos = prefix[pos];
			}
		}

    	return matches;
	}
};
//BEGIN CUT
int main()
{
	ifstream fin("strmatch.in");
	ofstream fout ("strmatch.out");

	Kmp kmp;
	string text;

	fin >> kmp.pattern >> text;
	kmp.preprocess_pattern();
	vector<int> matches = kmp.get_matches(text);

	fout << matches.size() << '\n';
	for (size_t i = 0; i < 1000 && i < matches.size(); ++i)
		fout << matches[i] << ' ';
	fout << '\n';

	fout.close();
	return 0;
}
//END CUT