Cod sursa(job #3156324)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 11 octombrie 2023 10:58:52
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

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

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

int main() {
	string t, s;
	fin >> t >> s;
	s = "." + t  + "." + s;
	vector<int> pi = kmp(s);
	int cnt = 0;
	vector<int> ans;
	for(int i = 1; i < (int) pi.size(); i++) {
		if(pi[i] == t.size()) {
			cnt++;
			if(cnt <= 1000) {
				ans.emplace_back(i - 2 * t.size() - 1);
			}
		}
	}
	fout << cnt << '\n';
	for(const auto &it: ans) {
		fout << it << " ";
	}
	return 0;
}