Cod sursa(job #1896758)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 28 februarie 2017 21:19:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <string.h>

#define NMax 2000001

using namespace std;

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

int pi[NMax], pLen, sLen, answ[NMax];
char str[NMax], pattern[NMax];

void compute_pi()
{
	int j = 0;
	for (int i = 2; i <= pLen; i++) {
		while (j != 0 && pattern[j + 1] != pattern[i])
			j = pi[j];

		if (pattern[j + 1] == pattern[i])
			j++;

		pi[i] = j;
	}
}

int main()
{
	f.getline(pattern + 1, NMax);
	f.getline(str + 1, NMax);

	sLen = strlen(str + 1);
	pLen = strlen(pattern + 1);

	compute_pi();

	int j = 0;
	for (int i = 1; i <= sLen; i++) {
		while (j != 0 && pattern[j + 1] != str[i])
			j = pi[j];

		if (pattern[j + 1] == str[i])
			j++;

		if (j == pLen) {
			++answ[0];
			if (answ[0] < 1000)
				answ[answ[0]] = i - pLen;
		}
	}

	g << answ[0] << '\n';
	for (int i = 1; i <= answ[0]; i++)
		g << answ[i] << ' ';
}