Cod sursa(job #2910663)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 23 iunie 2022 14:49:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda 3_iulie Marime 0.76 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;
}