Cod sursa(job #1833922)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 23 decembrie 2016 15:14:18
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 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];
int longPref[NMax], pos[1010], num, lenStr, lenPat;

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

		if (pattern[longPref[crt] + 1] == pattern[i])
			longPref[i] = longPref[crt] + 1;
		else
			longPref[i] = 0;
	}
}

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

			if (pattern[longPref[posPat] + 1] == str[i])
				posPat = longPref[posPat] + 1;
			else
				posPat = 0;
		}

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

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

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;
}