Cod sursa(job #2945277)

Utilizator MarcGrecMarc Grec MarcGrec Data 23 noiembrie 2022 17:40:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 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';
	for (int i = 0; i < ((k < 1000) ? k : 1000); ++i)
		fout << r[i] << ' ';
    fin.close();
    fout.close();
    return 0;
}