Cod sursa(job #2356087)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 26 februarie 2019 14:54:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[2000001], b[2000001];
int p[2000001], k = 0, pos[1001];


void pref()
{
	int l = 0;
	for (int i = 1; b[i];)
	{
		if (b[i] == b[l])
		{
			l++;
			p[i] = l;
			i++;
		}
		else if (l)
			l = p[l - 1];
		else
		{
			p[i] = 0;
			i++;
		}
	}
}

void kmp()
{
	for (int i = 0, j = 0; a[i];)
	{
		if (a[i] == b[j])
			i++, j++;
		if (!b[j])
		{
			pos[k++] = i - j;
			j = p[j - 1];
		}
		else if (a[i] && a[i] != b[j])
		{
			if (j) j = p[j - 1];
			else i++;
		}
	}
}

int main()
{
	f.getline(b, 2000001);
	f.getline(a, 2000001);
	pref();
	kmp();
	g << k << "\n";
	k = (k < 1000 ? k : 1000);
	for (int i = 0; i < k; i++)
		g << pos[i] << " ";
	return 0;
}