Cod sursa(job #2899185)

Utilizator AlexNeaguAlexandru AlexNeagu Data 8 mai 2022 02:10:48
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 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;
	vector<int> sol;
	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 = preFunc[k - 1];
		}
		if(k != 0) {
			preFunc[i] = k + 1;
		} else {
			preFunc[i] = P[0] == P[k] ? 1 : 0;
		}
	}
	int i = 0, k = 0, answer = 0;
	while(i + m - 1 < n) {
		if(k != m && P[k] == T[i + k]) {
			k++;
		} else if(k > 0) {
			if(k == m) {
				answer++;
				if(sol.size() < 1000) {
					sol.push_back(i);
				}
			}
			i += k - preFunc[k - 1];
			k = preFunc[k - 1];
		} else {
			i++;
		}
	}
	out << answer << '\n';
	for(auto it : sol) {
		out << it << ' ';
	}
}