Cod sursa(job #3333138)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 11 ianuarie 2026 12:57:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>

using namespace std;

const int nmax = 2e6 + 5;
const string txt = "strmatch";

ifstream f(txt + ".in");
ofstream g(txt + ".out");

int l[nmax];
string a, b;
vector<int> ans;

void lps()
{
	int i = 1, j = 0;
	while (i < a.size())
	{
		if (a[i] == a[j]) l[i] = j + 1, i++, j++;
		else
		{
			if (j > 0) j = l[j - 1];
			else i++;
		}
	}
}

int main()
{
	f >> a >> b;
	lps();

	int i = 0, j = 0;
	while (i < b.size())
	{
		if (a[j] == b[i]) {
			i++; j++;
			if (j == a.size()) ans.push_back(i - j), j = l[j - 1];
		}

		else
		{
			if (j != 0) j = l[j - 1];
			else i++;
		}
	}

	g << ans.size() << '\n';
	for(int i = 0; i < min(1000, (int)ans.size()); i++) g << ans[i] << " ";
	return 0;
}