Cod sursa(job #3228363)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 7 mai 2024 18:41:17
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;

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

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