Cod sursa(job #3142422)

Utilizator dragoncrackCandidatu Mario Luca dragoncrack Data 21 iulie 2023 10:56:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char a[2000001], b[2000001], A[2000001], B[2000001];
int p[2000001], l, sol, solutii[1001];

int main()
{
	fin >> a >> b;
	int n = strlen(a);
	int m = strlen(b);
	strcpy(A + 1, a);
	strcpy(B + 1, b);
	p[1] = 0;
	l = 0;
	for (int i = 2; i <= n; 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 <= m; i++)
	{
		while (l != 0 && B[i] != A[l + 1])
			l = p[l];
		if (B[i] == A[l + 1])
			l++;
		if (l == n)
		{
			sol++;
			if (sol <= 1000)
			{
				solutii[sol] = i - n;
			}
			l = p[l];
		}
	}
	fout << sol << "\n";
	for (int i = 1; i <= sol; i++)
	{
		if (i > 1000)
			break;
		fout << solutii[i] << " ";
	}
}