Cod sursa(job #3187359)

Utilizator tomaionutIDorando tomaionut Data 28 decembrie 2023 16:58:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

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

char s1[2000005], s2[2000005];
int lps[2000005], n, m;
vector <int> sol;
int32_t main()
{
	int i, j;
	fin >> s1 >> s2;
	n = strlen(s1);
	m = strlen(s2);
	i = 1;
	j = 0;
	while (i < n)
	{
		if (s1[i] == s1[j])
		{
			lps[i] = j + 1;
			i++; 
			j++;
		}
		else
		{
			if (j) j = lps[j - 1];
			else i++;
		}
	}

	i = j = 0;
	while (i < m)
	{
		if (s2[i] == s1[j])
		{
			i++;
			j++;
		}
		else
		{
			if (j) j = lps[j - 1];
			else i++;
		}

		if (j == n)
		{
			sol.push_back(i - n);
			j = lps[j - 1];
		}
	}

	fout << sol.size() << "\n";
	j = sol.size();
	for (i = 0; i < min(1000, j); i++)
		fout << sol[i] << " ";
	

	

	return 0;
}