Cod sursa(job #2910658)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 23 iunie 2022 13:05:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstring>

#define DIM 2000002

using namespace std;

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

char a[DIM], b[DIM];
int p[DIM];
int n = 0, sol[1001];

int main()
{
	fin >> (a + 1) >> (b + 1);
	int lenA = strlen(a + 1);
	int lenB = strlen(b + 1);

	int L = 0;
	p[1] = 0;
	for (int i = 2; i <= lenA; i++)
	{
		while (L != 0 && a[i] != a[L + 1])
			L = p[L];
		if (a[i] == a[L + 1])
			L++;
		p[i] = L;
	}

	L = 0;
	for (int i = 1; i <= lenB; i++)
	{
		while (L != 0 && b[i] != a[L + 1])
			L = p[L];
		if (b[i] == a[L + 1])
			L++;

		if (L == lenA)
		{
			n++;
			if (n <= 1000)
				sol[n] = i - lenA;
			L = p[L];
		}
	}

	fout << n << '\n';
	for (int i = 1; i <= min(n, 1000); i++)
		fout << sol[i] << ' '; 

	return 0;
}