Cod sursa(job #2806768)

Utilizator Langa_bLanga Radu Langa_b Data 22 noiembrie 2021 23:07:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s1, s2;
long long l1, l2, len;
vector<long long> lps, rezi;
int main() {
	cin >> s1;
	l1 = s1.size();
	cin.get();
	cin >> s2;
	l2 = s2.size();
	lps.emplace_back(0);
	long long i = 1;
	long long rez = 0;
	while (i < l1) {
		rez = 0;
		if (s1[i] == s1[len]) {
			len++;
			lps.emplace_back(len);
			i++;
		}
		else {
			if (len != 0) {
				len = lps[len - 1];
			}
			else {
				lps.emplace_back(len);
				i++;
			}
		}
	}
	i = 0;
	long long j = 0, cnt = 0;
	while (i < l2) {
		if (s1[j] == s2[i]) {
			i++;
			j++;
		}
		if (j == l1) {
			cnt++;
			rezi.emplace_back(i - j);
			j = lps[j - 1];
		}
		if (s1[j] != s2[i]) {
			if (j != 0) {
				j = lps[j - 1];
			}
			else {
				i++;
			}
		}
	}
	cout << cnt<<'\n';
	for (int k = 0; k < rezi.size(); k++) {
		if (k < 1000) {
			cout << rezi[k] << ' ';
		}
	}
}