Cod sursa(job #2899014)

Utilizator AlexNeaguAlexandru AlexNeagu Data 7 mai 2022 15:35:14
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
	string P;
	in >> P;
	string T;
	in >> T;
	int answer[1001], L = 0;
	int n = T.size();
	int m = P.size();
	vector<int> preFunc(m, 0);
	for(int i = 1; i < m; ++i) {
		int k = preFunc[i - 1];
		while(k && P[k] != P[i]) {
			k = P[k - 1];
		}
		if(P[k] == P[i]) {
			k++;
		}
		preFunc[i] = k;
	}
	int 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[k - 1];
			L++;
			if(L <= 1000) {
				answer[L] = i - m + 1;
			}
		}
	}
	
	out << min(L, 1000) << '\n';
	for(int i = 1; i <= L; ++i) {
		out << answer[i] << ' ';
	}
}