Cod sursa(job #2803446)

Utilizator lucamLuca Mazilescu lucam Data 20 noiembrie 2021 00:21:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");

constexpr int MAXCNT = 1e3;

std::vector<int> kmp(const std::string &s) {
	std::vector<int> pi(s.size());
	pi[0] = 0;
	for (int i = 1; i < int(s.size()); ++i) {
		int last = pi[i - 1];
		while (last != 0 && s[i] != s[last]) {
			last = pi[last - 1];
		}
		if (s[i] != s[last]) {
			last = -1;
		}
		pi[i] = last + 1;
	}
	return pi;
}

int main() {
	std::string a, b;
	in >> a >> b;
	auto pi = kmp(a + "#" + b);
	auto start = pi.begin() + a.size() + 1;
	int cnt = std::count(start, pi.end(), a.size());
	out << cnt << "\n";
	cnt = std::min(cnt, MAXCNT);
	for (auto it = start; it != pi.end() && cnt >= 1; ++it) {
		if (*it == int(a.size())) {
			out << it - start - a.size() + 1 << " ";
			--cnt;
		}
	}
	out << "\n";
}