Cod sursa(job #2356168)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 26 februarie 2019 15:49:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <cstring>
using namespace std;

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

char a[2000005], b[2000005];
int p[2000005], k = 0, pos[1001], la, lb;


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

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

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