Cod sursa(job #2941546)

Utilizator rastervcrastervc rastervc Data 17 noiembrie 2022 20:59:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

constexpr size_t LIM = 2e6 + 5;

char pat[LIM], txt[LIM];
int lps[LIM], N, M;
vector<int> ans;

static inline void compute_lps() {
	lps[0] = 0;
	int len = 0, i = 1;
	while (i < M) {
		if (pat[i] == pat[len]) {
			len++;
			lps[i] = len;
			i++;
		} else {
			if (len != 0)
				len = lps[len - 1];
			else {
				lps[i] = 0;
				i++;
			}
		}
	}
}

static inline void kmp() {
	int i = 0, j = 0;
	while ((N - i) >= (M - j)) {
		if (pat[j] == txt[i])

			i++, j++;
		if (j == M) {
			if (ans.size() < 1000)
				ans.push_back(i - j);
			j = lps[j - 1];
		} else if(i < N && pat[j] != txt[i]) {
			if (j != 0) j = lps[j - 1];
			else i++;
		}
	}
}

int main(void) {
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");

	fin >> pat >> txt;
	N = strlen(txt);
	M = strlen(pat);

	compute_lps();
	kmp();

	fout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		fout << ans[i] << ' ';

	fin.close();
	fout.close();
	return 0;
}