Cod sursa(job #936439)

Utilizator forgetHow Si Yu forget Data 7 aprilie 2013 09:50:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
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;
	}
	int cnt = 0;
	int ans[1000];
	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) {
			if (cnt < 1000) ans[cnt] = i-length;
			++cnt;
		}
	}
	fout << cnt << '\n';
	if (cnt > 1000) cnt = 1000;
	for (int i = 0; i < cnt; ++i)
		fout << ans[i] << ' ';
	return 0;
}