Cod sursa(job #2723134)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 13 martie 2021 16:26:01
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <string>
using namespace std;

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

int p[4000001];
string a, b;

int main()
{
	int rasp[1001];
	rasp[0] = 0;
	int n, m, i, j;
	fin >> a >> b;
	n = a.size();
	m = b.size();
	a = a + '#' + b;
	
	for (i = 1; i < n+m; i++)
	{
		j = p[i-1];
		while (j > 0 && a[i] != a[j])
			j = p[j-1];
		if (a[i] == a[j])
			j++;
		p[i] = j;
		
		if (p[i] == n)
		{
			rasp[0]++;
			if (rasp[0] < 1000)
				rasp[rasp[0]] = i - 2 * n;
		}
	}
	fout << rasp[0] << '\n';
	for (i = 1; i<=min(rasp[0], 1000); i++)
		fout << rasp[i] << ' ';
	return 0;
}