Cod sursa(job #2425852)

Utilizator urweakurweak urweak Data 25 mai 2019 10:35:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#define LMAX 2000002

using namespace std;

char txt[LMAX], pat[LMAX];
int n, m, nsol, sol[1001], pi[LMAX];

void make_prefix()
{
	int k = 0;
	for(int q = 2; q <=m; q++)
	{
		while(k > 0 && pat[k+1] != pat[q]) k = pi[k];
		if(pat[k+1] == pat[q]) k++;
		pi[q] = k;
	}
}

int main()
{
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	fin >> (pat + 1);
	fin >> (txt + 1);
	n = strlen(txt + 1);
	m = strlen(pat + 1);
	make_prefix();
	int q = 0;
	for(int i = 1; i<=n; i++)
	{
		while(q > 0 && txt[i] != pat[q+1]) q = pi[q];
		if(txt[i] == pat[q+1]) ++q;
		if(q == m)
		{
			q = pi[m];
			++nsol;
			if(nsol <= 1000)sol[nsol] = i - m;
		}
	}
	fout << nsol <<'\n';
	for(int i = 1; i<=min(nsol, 1000); i++)
		fout << sol[i] <<' ';
}