Cod sursa(job #3372655)

Utilizator mihalachecostin.danielMihalache Costin-Daniel mihalachecostin.daniel Data 4 noiembrie 2026 16:53:33
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");



int main()
{
	string A, B;
	f >> A >> B;
	int n = A.size();
	int m = B.size();
	vector<int> pi(n, 0);
	int k = 0;
	for (int i = 1;i < n;i++)
	{
		while (k > 0 && A[i] != A[k])
			k = pi[k - 1];
		if (A[i] == A[k])
			k++;
		pi[i] = k;
	}

	vector<int> pozitii;
	int count = 0;
	k = 0;
	for (int i = 0;i < m;i++)
	{
		while (k > 0 && B[i] != A[k])
			k = pi[k - 1];
		if (B[i] == A[k])
			k++;
		if (k == n)
		{
			count++;
			if (pozitii.size() < 1000)
				pozitii.push_back(i - n + 1);
			k = pi[k - 1];
		}
	}
	g << count << "\n";
	for (int p : pozitii)
		g << p << "";
	g << "\n";
}