Cod sursa(job #185873)

Utilizator tvladTataranu Vlad tvlad Data 26 aprilie 2008 12:10:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void prefix ( const string &a, vector<int> &pi ) {
	pi.resize(a.size());
	pi[0] = -1;
	int i;
	int k;
	for (i = 1, k = -1; i < a.size(); ++i) {
		for (; k >= 0 && a[i] != a[k+1]; k = pi[k]);
		if (a[i] == a[k+1]) {
			++k;
			pi[i] = k;
		} else {
			pi[i] = -1;
		}
	}
}

void search ( const string &what, const string &where, vector<int> &ret ) {
	vector<int> pi;
	prefix(what,pi);
	for (int i = 0, k = -1; i < where.size(); ++i) {
//		fout << i << ": k = " << k;
		for (; k >= 0 && where[i] != what[k+1]; k = pi[k]);
//		fout << " -> " << k << "\n";
		if (where[i] == what[k+1]) {
			++k;
			if (k == what.size()-1) {
				ret.push_back(i-k);
				k = pi[k];
			}
		} else {
			k = -1;
		}
	}
}

int main() {
	string a,b;
	fin >> a >> b;
	vector<int> ap;
	search(a,b,ap);
	fout << ap.size() << "\n";
	for (int i = 0; i < ap.size() && i < 1000; ++i) fout << ap[i] << " ";
	return 0;
}