Rezultati

Up. imeNalogaJezikRezultatČas oddaje
lisperator-2017 Pasavci C++ 0/100Prekoračen čas (TLE) 11. maj '17 @ 19:22

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,223 MiB 0,004 s OK
#2 5/5 3,195 MiB 0,004 s OK
#3 5/5 3,223 MiB 0,004 s OK
#4 5/5 3,195 MiB 0,004 s OK
#5 5/5 3,223 MiB 0,004 s OK
#6 5/5 3,199 MiB 0,004 s OK
#7 5/5 3,199 MiB 0,010 s OK
#8 5/5 3,223 MiB 0,004 s OK
#9 6/6 3,215 MiB 0,004 s OK
#10 0/6 4,223 MiB 1,496 s Prekoračen čas
#11 6/6 3,219 MiB 0,004 s OK
#12 6/6 3,188 MiB 0,004 s OK
#13 6/6 3,199 MiB 0,004 s OK
#14 6/6 3,199 MiB 0,004 s OK
#15 0/6 3,219 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​917497
<<<EOF>>>
Pravilen izhod:
​1048567
<<<EOF>>>
#16 6/6 3,195 MiB 0,004 s OK
#17 6/6 3,215 MiB 0,004 s OK
#18 0/6 4,156 MiB 1,514 s Prekoračen čas

Ocenjevani program (Source.cpp):
#include <iostream>
#include <string>

using namespace std;

string gen;

void BCH(string pattern, int*& bch) {
	bch = new int[256];
	for (int x = 0; x < 256; x++) {
		bch[x] = pattern.length() + 1;
	}

	for (int x = 0; x < pattern.length(); x++) {
		bch[pattern[x]] = pattern.length() - x;
	}
}

int Sunday(string file, string pattern) {
	int count = 0;
	int* bch;
	BCH(pattern, bch);

	int i = 0;
	int pos = 0;
	while (pos <= file.length() - pattern.length()) {
		while (i < pattern.length()) {
			if (pattern[i] != file[pos + i]) {
				break;
			}
			i++;
		}
		if (i == pattern.length()) {
			count++;
		}
		pos += bch[file[pos + pattern.length()]];
		i = 0;
	}

	delete[] bch;
	return count;
}

class Pasavec {
	public:
		Pasavec() {
			aGeneCount = 0;
			start = "";
			end = "";
		}

		Pasavec(string s) {
			if (s.length() < gen.length()) {
				start = s;
				end = s;
				aGeneCount = 0;
			} else {
				start = s.substr(0, gen.length() - 1);
				end = s.substr(s.length() - gen.length() + 1, gen.length() - 1);
				aGeneCount = Sunday(s, gen);
			}
		}

		Pasavec(Pasavec p1, Pasavec p2) {
			aGeneCount = p1.aGeneCount + p2.aGeneCount;
			string temp = "";
			if (p1.end.length() == gen.length()) {
				temp += p1.end.substr(1);
			} else {
				temp += p1.end;
			}
			if (p2.start.length() == gen.length()) {
				temp += p2.start.substr(0, p2.start.length() - 1);
			} else {
				temp += p2.start;
			}
			if (p1.end.length() + p2.start.length() <= gen.length()) {
				start = p1.start + p2.end;
				end = start;
				if (p1.end.length() + p2.start.length() == gen.length()) {
					aGeneCount += Sunday(temp, gen);
				}
			} else {
				start = p1.start;
				end = p2.end;
				aGeneCount += Sunday(temp, gen);
			}
		}

		string start, end;
		int aGeneCount;
};

int main() {

	cin >> gen;
	string s1, s2;
	cin >> s1 >> s2;
	Pasavec pasavci[1002];
	pasavci[0] = Pasavec(s1);
	pasavci[1] = Pasavec(s2);
	int m;
	cin >> m;
	int a, b;
	int i;
	for (i = 2; i < m + 2; ++i) {
		cin >> a >> b;
		pasavci[i] = Pasavec(pasavci[a - 1], pasavci[b - 1]);
	}
	cout << pasavci[i - 1].aGeneCount << endl;

	//system("pause");
	return 0;
}