Cod sursa(job #1908929)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 11:00:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nMax = 2e6 + 2;

int n, m;
string a, b, s;

vector<int>Kmp(const string &that) {
	vector<int>pi(that.size(), -1);

	for (int i = 1; i < that.size(); ++i) {
		int j = pi[i - 1];

		while (j >= 0 and that[j + 1] != that[i]) {
			j = pi[j];
		}

		if (that[j + 1] == that[i])
			j++;

		pi[i] = j;
	}

	return pi;
}

int main() {
	fin >> a >> b;
	s = a + '$' + b;
	auto pi = Kmp(s);
	vector<int>match;

	for (int i = a.size(); i < s.size(); ++i) {
		if (pi[i] == a.size() - 1 and match.size() + 1 <= 1000) {
			match.push_back(i - 2 * a.size());
		}
	}

	fout << match.size() << '\n';

	for (const auto& itr : match)
		fout << itr << ' ';
	return 0;
}