Rezultati

Up. imeNalogaJezikRezultatČas oddaje
finalsolution-2017 Pasavci C++ 100/100OK 11. maj '17 @ 18:30

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,258 MiB 0,004 s OK
#2 5/5 3,277 MiB 0,004 s OK
#3 5/5 3,250 MiB 0,004 s OK
#4 5/5 3,250 MiB 0,004 s OK
#5 5/5 3,313 MiB 0,004 s OK
#6 5/5 3,363 MiB 0,004 s OK
#7 5/5 3,316 MiB 0,004 s OK
#8 5/5 3,324 MiB 0,004 s OK
#9 6/6 3,324 MiB 0,004 s OK
#10 6/6 5,254 MiB 0,174 s OK
#11 6/6 3,254 MiB 0,004 s OK
#12 6/6 3,258 MiB 0,004 s OK
#13 6/6 3,250 MiB 0,004 s OK
#14 6/6 3,254 MiB 0,004 s OK
#15 6/6 3,215 MiB 0,004 s OK
#16 6/6 3,211 MiB 0,004 s OK
#17 6/6 3,090 MiB 0,004 s OK
#18 6/6 5,289 MiB 0,174 s OK

Ocenjevani program (pasavci.cpp):
#include <stdio.h>
#include <stdlib.h>

#include <vector>
#include <iostream>

struct pasavec {
    bool m_didslice;
    long long m_reps;
    std::string m_value;
    std::string m_prefix;
    std::string m_suffix;
    void init(const std::string &str);
    void init(const pasavec &a, const pasavec &b);
    void add_count(const std::string &str);
};

typedef struct pasavec pasavec_t;

std::string s_pattern;
std::vector<pasavec_t> s_pasavci;

void pasavec::init(const std::string &str) {
    if (str.size() < s_pattern.size()) {
        this->m_didslice = false;
        this->m_value = str;
        return;
    }
    this->m_didslice = true;
    this->m_reps = 0;
    this->m_prefix = str.substr(0, s_pattern.size() - 1);
    this->m_suffix = str.substr(str.size() - s_pattern.size() + 1);
    this->add_count(str);
}

void pasavec::init(const pasavec &a, const pasavec &b) {
    if (!a.m_didslice && !b.m_didslice) {
        std::string str = a.m_value + b.m_value;
        this->init(str);
        return;
    }
    if (!a.m_didslice) {
        std::string str = a.m_value + b.m_prefix;
        this->m_didslice = true;
        this->m_reps = b.m_reps;
        this->m_prefix = str.substr(0, s_pattern.size() - 1);
        this->m_suffix = b.m_suffix;
        this->add_count(str);
        return;
    }
    if (!b.m_didslice) {
        std::string str = a.m_suffix + b.m_value;
        this->m_didslice = true;
        this->m_reps = a.m_reps;
        this->m_prefix = a.m_prefix;
        this->m_suffix = str.substr(str.size() - s_pattern.size() + 1);
        this->add_count(str);
        return;
    }
    std::string str = a.m_suffix + b.m_prefix;
    this->m_didslice = true;
    this->m_reps = a.m_reps + b.m_reps;
    this->m_prefix = a.m_prefix;
    this->m_suffix = b.m_suffix;
    this->add_count(str);
}

void pasavec::add_count(const std::string &str) {
    size_t pos = str.find(s_pattern);
    while (pos != std::string::npos) {
        this->m_reps++;
        pos = str.find(s_pattern, pos + 1);
    }
    this->m_reps %= 1000000007;
}

int main() {
    int k = 1, m = 0;
    std::string g1, g2;
    std::cin >> s_pattern;
    std::cin >> g1;
    std::cin >> g2;
    std::cin >> m;
    s_pasavci.resize(m + 3);
    s_pasavci[1].init(g1);
    s_pasavci[2].init(g2);
    for (; k <= m; k++) {
        int a = 0, b = 0;
        std::cin >> a >> b;
        pasavec &ps = s_pasavci[k+2];
        ps.init(s_pasavci[a], s_pasavci[b]);
    }
    pasavec &ps = s_pasavci[m+2];
    if (!ps.m_didslice) ps.add_count(ps.m_value);
    printf("%lld\n", ps.m_reps);
    return 0;
}