Cod sursa(job #2365240)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 4 martie 2019 12:39:31
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 b[20000001];
long long p[20000001], k = 0, pos[1001];


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

void kmp()
{
	int l = 0, i = 1;
	char c;
	c = f.get();
	while (!(c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z' || c >= '0' && c <= '9')) 
		c = f.get();
	while (c != EOF)
	{
		while (l && b[l] != c)
			l = p[l - 1];
		if (b[l] == c) l++;
		if (b[l] == 0)
			pos[k++] = i - l;
		i++;
		c = f.get();
	}
}

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