Cod sursa(job #2868353)

Utilizator alextmAlexandru Toma alextm Data 10 martie 2022 21:14:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2e6 + 5;

string text, pattern;
int pi[MAXN], ans[MAXN], cnt;

int main() {
	fin >> pattern >> text;
	
	int n = (int) text.length();
	int m = (int) pattern.length();
	text = '$' + text;
	pattern = '$' + pattern;
	
	for(int i = 2, q = 0; i <= m; i++) {
		while(q && pattern[q + 1] != pattern[i])
			q = pi[q];
		if(pattern[q + 1] == pattern[i])
			q++;
		pi[i] = q;
	}
	
	for(int i = 1, q = 0; i <= n; i++) {
		while(q && pattern[q + 1] != text[i])
			q = pi[q];
		if(pattern[q + 1] == text[i])
			q++;
		if(q == m) {
			q = pi[q];
			cnt++;
			if(cnt <= 1000)
				ans[cnt] = i - m;
		}
	}
	
	fout << cnt << '\n';
	for(int i = 1; i <= min(cnt, 1000); i++)
		fout << ans[i] << ' ';
	fout << '\n';
	
	return 0;
}