Cod sursa(job #2945284)

Utilizator MarcGrecMarc Grec MarcGrec Data 23 noiembrie 2022 17:44:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#define MAX_LENGTH 2000000

#include <fstream>
using namespace std;

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

char a[MAX_LENGTH + 1], b[MAX_LENGTH + 1];
int t[MAX_LENGTH], r[1000];

int main()
{
	fin >> a >> b;
	for (int i = 1, j = 0; a[i];)
	{
		while (a[i] == a[j])
		{
			t[i] = ++j;
			++i;
		}
		if (j)
			j = t[j - 1];
		else
			++i;
	}
	int k = 0;
	for (int i = 0, j = 0; b[i];)
	{
		while (a[j] && (b[i] == a[j]))
		{
			++i;
			++j;
		}
		if (!a[j] && ((++k) <= 1000))
			r[k - 1] = i - j;
		if (j)
			j = t[j - 1];
		else
			++i;
	}
	fout << k << '\n';
	if (k > 1000)
		k = 1000;
	for (int i = 0; i < k; ++i)
		fout << r[i] << ' ';
    fin.close();
    fout.close();
    return 0;
}