Cod sursa(job #2922257)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 7 septembrie 2022 12:03:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

const int LEN_MAX = 2e6 + 5;

string A, B;
int pi[LEN_MAX];

vector <int> Ans;

int main() {
	ios_base::sync_with_stdio(false);
	fin.tie(NULL);
	fout.tie(NULL);

	fin >> A >> B;
	A = " " + A;
	B = " " + B;
	pi[1] = 0;
	int k = 0;
	for (int i = 2; i < A.size(); i++) {
		while (k > 0 && A[i] != A[k + 1]) {
			k = pi[k];
		}
		if (A[i] == A[k + 1]) {
			k++;
		}
		pi[i] = k;
	}

	int q = 0;
	for (int i = 1; i < B.size(); i++) {
		while (q > 0 && A[q + 1] != B[i]) {
			q = pi[q];
		}
		if (A[q + 1] == B[i]) {
			q++;
		}
		if (q == A.size() - 1) {
			Ans.push_back(i - A.size() + 1);
		}
	}

	fout << Ans.size() << "\n";
	for (int pos : Ans) {
		fout << pos << " ";
	}
	return 0;
}