Cod sursa(job #2899179)

Utilizator AlexNeaguAlexandru AlexNeagu Data 8 mai 2022 01:54:35
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<vector>
#include<string>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

int preFunc[2000005];
int answer[1001], L = 0;

int main() {
	ios_base::sync_with_stdio(false);
	
	string P;
	string T;
	in >> P >> T;
	int n = T.size();
	int m = P.size();
	
	preFunc[0] = 0;
	int k = 0;
	
	for(int i = 1; i < m; ++i) {
		while(k && P[k] != P[i]) {
			k = P[k - 1];
		}
		if(P[k] == P[i]) {
			k++;
		}
		preFunc[i] = k;
	}
	
	k = 0;
	for(int i = 0; i < n; ++i) {
		while(k && P[k] != T[i]) {
			k = preFunc[k - 1];
		}
		if(P[k] == T[i]) {
			k++;
		}
		if(k == m) {
			k = preFunc[m - 1];
			L++;
			if(L <= 1000) {
				answer[L] = i - m + 1;
			}
		}
	}
	
	out << L << '\n';
	for(int i = 1; i <= min(L, 1000); ++i) {
		out << answer[i] << ' ';
	}
}