Cod sursa(job #1094757)

Utilizator cdt2014Cont de Teste cdt2014 Data 29 ianuarie 2014 20:06:36
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define trace(X) cout << #X << "=" << X << endl

class KMP {
	public:
		KMP(string pattern) : prefix(1 + pattern.length()), pattern(" " + pattern) {
			int k = 0;
			for (int i=2; i<this->pattern.length(); ++i) {
				// trace(i);
				// trace(k);
				while (k > 0 && this->pattern[k] != this->pattern[i]) {
					// trace(k);
					k = prefix[k];
				}

				if (this->pattern[k+1] == this->pattern[i]) {
					k ++;
				}

				prefix[i] = k;
			}

			//for (int i=0; i<prefix.size(); ++i)
			//	cout << prefix[i] << " ";
			//cout << endl;
		}

		vector<int> match(string text) {
			text = " " + text;
			vector<int> result;
			int k = 0;
			for (int i=1; i<text.length(); ++i) {
				while (k > 0 && pattern[k+1] != text[i]) {
					k = prefix[k];
				}

				if (pattern[k+1] == text[i]) {
					k ++;
				}

				if (k == pattern.length() - 1) {
					result.push_back(i - pattern.length() + 1);
				}
			}
			return result;
		}

	private:
		vector<int> prefix;
		string pattern;
};

int main() {
	ifstream in("strmatch.in");
	ofstream out("strmatch.out");

	string A, B;
	in >> A >> B;

	KMP kmp(A);
	vector<int> pos = kmp.match(B);

	int m = 100 < pos.size() ? 100 : pos.size();
	out << pos.size() << "\n";
	for (int i=0; i<m; ++i) {
		out << pos[i] << " ";
	}
	out << "\n";

	return 0;
}