Cod sursa(job #2425083)

Utilizator urweakurweak urweak Data 24 mai 2019 11:37:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#define LMAX 2000002

using namespace std;

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

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

}

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