Cod sursa(job #936437)

Utilizator forgetHow Si Yu forget Data 7 aprilie 2013 09:17:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
using namespace std;

int main() {
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	string word;
	fin >> word;
	int length = word.size();
	int a[length];
	int b;
	a[0] = -1;
	for (int i = 1; i < length; ++i) {
		b = a[i-1];
		while (b != -1 && word[b+1] != word[i]) b = a[b];
		++b;
		a[i] = word[b] == word[i]? b : -1;
	}
	vector<int> ans;
	b = -1;
	--length;
	char c;
	for (int i = 0; fin >> c; ++i) {
		while (b != -1 && word[b+1] != c) b = a[b];
		if (word[b+1] == c) ++b;
		if (b == length) ans.push_back(i-length);
	}
	fout << ans.size() << '\n';
	for (vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)
		fout << *it << ' ';
	return 0;
}