Cod sursa(job #3309118)

Utilizator InsanekktVlad Matei Insanekkt Data 1 septembrie 2025 14:37:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

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

vector<int> LPS(string& s) {
	vector<int> lps;
	int n = s.length();
	lps.resize(n);

	int i = 1, len=0;
	while (i < n) 
		if (s[i] == s[len]) 
			lps[i++] = ++len;
		else 
			if (len != 0)  
				len = lps[len - 1];
			else 
				lps[i++] = 0;
			
	return lps;
}

int main() {
	string pat, txt;
	getline(in, pat);
	getline(in, txt);

	vector<int> ans, lps;
	int n = pat.length(), m = txt.length(), i = 0, len = 0;
	lps = LPS(pat);
	
	while (i < m) {
		if (pat[len] == txt[i]) {
			++i; 
			++len;
		}
		if (len == n) {
			ans.push_back(i - len);
			len = lps[len - 1];
		}
		else 
			if (i < m && pat[len] != txt[i]) 
				if (len != 0) 
					len = lps[len - 1];
				else 
					++i;
	}

	out << ans.size() << endl;
	int newsize = min((int)ans.size(), 1000);
	for (int i = 0; i < newsize; ++i) {
		out << ans[i] << " ";
	}
	
}