Cod sursa(job #3151425)

Utilizator mihai.alphamihai craciun mihai.alpha Data 21 septembrie 2023 11:31:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cctype>
#include <vector>

const int maxlen = 2e6 + 1;

std::string A, B;
int N, M;

int pi[maxlen];
int d[maxlen];
std::vector <int> ans;

int main()  {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	std::cin >> A >> B;
	N = A.size();
	M = B.size();
	A.insert(0, 1, 0);
	B.insert(0, 1, 0);
	pi[1] = 0;
	for(int i = 2;i <= N;i++)  {
		int aux = pi[i - 1];
		while(aux && A[i] != A[aux + 1])
			aux = pi[aux];
		if(A[i] == A[aux + 1])
			aux++;
		pi[i] = aux;
	}
	for(int i = 1;i <= M;i++)  {
		int aux = d[i - 1];
		while(aux && B[i] != A[aux + 1])
			aux = pi[aux];
		if(B[i] == A[aux + 1])
			aux++;
		d[i] = aux;
		if(d[i] == N && ans.size() < 1000)  {
			ans.push_back(i - N);
		}
	}
	printf("%zu\n", ans.size());
	for(const auto &x : ans)
		printf("%d ", x);
	printf("\n");
	return 0;
}