Cod sursa(job #1833853)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 23 decembrie 2016 13:12:39
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <string.h>
#include <vector>

#define NMax 2000010

using namespace std;

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

char str[NMax], pattern[NMax], lenStr, lenPat;
int longPref[NMax], pos[1010], num;

void computeLongestPrefSuf()
{
	longPref[1] = 0;
	int crt = 0;
	for (int i = 2; i <= lenPat; i++) {
		while (crt > 0 && pattern[crt + 1] != pattern[i])
			crt = longPref[crt];

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

		longPref[i] = crt;
	}
}

void computeNumberOfOcc()
{
	int posPat = 0;
	for (int i = 1; i <= lenStr; i++) {
		while (posPat > 0 && pattern[posPat + 1] != str[i])
			posPat = longPref[posPat];

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

		if (posPat == lenPat) {
			num++;

			if (num < 1000)
				pos[num] = i - lenPat;
		}
	}
}

int main()
{
	f >> (pattern + 1);
	f >> (str + 1);

	lenPat = strlen(pattern + 1);
	lenStr = strlen(str + 1);

	computeLongestPrefSuf();
	computeNumberOfOcc();

	g << num << "\n";
	for (int i = 1; i <= num && i <= 1000; i++)
		g << pos[i] << " ";

	return 0;
}