Rezultati

Up. imeNalogaJezikRezultatČas oddaje
pitoni-2017 Pasavci C++ 100/100OK 11. maj '17 @ 19:28

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,164 MiB 0,004 s OK
#2 5/5 3,215 MiB 0,004 s OK
#3 5/5 3,234 MiB 0,004 s OK
#4 5/5 3,246 MiB 0,004 s OK
#5 5/5 3,254 MiB 0,004 s OK
#6 5/5 3,367 MiB 0,004 s OK
#7 5/5 3,297 MiB 0,010 s OK
#8 5/5 3,270 MiB 0,004 s OK
#9 6/6 3,270 MiB 0,004 s OK
#10 6/6 12,898 MiB 0,037 s OK
#11 6/6 3,227 MiB 0,004 s OK
#12 6/6 3,227 MiB 0,004 s OK
#13 6/6 3,141 MiB 0,004 s OK
#14 6/6 3,141 MiB 0,004 s OK
#15 6/6 3,145 MiB 0,004 s OK
#16 6/6 3,227 MiB 0,004 s OK
#17 6/6 3,160 MiB 0,004 s OK
#18 6/6 12,902 MiB 0,039 s OK

Ocenjevani program (pas.cpp):
#include <algorithm>
#include <array>
#include <complex>
#include <cmath>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef unsigned long long ull;

string p;
int lp;

int MOD = 1000000007;

struct Mute {
    long long cnt;
    string beg, end;
    vector<int> spr, zad;
    
    Mute(string s1, string s2) : beg(s1), end(s2), cnt(0) {
        for (int i = 1; i < p.size() && i <= s1.size(); ++i) {
            if (p.substr(lp-i, i) == s1.substr(0, i)) {
                spr.push_back(i);
            }
        }
        for (int i = 1; i < p.size() && i <= s2.size(); ++i) {
            if (p.substr(0, i) == s2.substr(s2.size()-i, i)) {
                zad.push_back(i);
            }
        }
        int idx = s1.find(p);
        while (idx != string::npos) {
            idx = s1.find(p, idx+1);
            cnt++;
        }
    }
    
    Mute(const Mute& m1, const Mute& m2) {
        cnt = m1.cnt + m2.cnt;
        cnt %= MOD;
        end = m1.end+m2.end;
        if (end.size() > lp) { end = end.substr(end.size()-lp, lp); }
        beg = m1.beg+m2.beg;
        if (beg.size() > lp) { beg = beg.substr(0, lp); }
        
        int i = 0, j = m2.spr.size()-1;
        while (i < m1.zad.size() && j >= 0) {
            if (m1.zad[i] + m2.spr[j] == lp) {
                cnt++;
                j--;
                i++;
            } else if (m1.zad[i] + m2.spr[j] > lp) {
                j--;
            } else {
                i++;
            }
        }
        cnt %= MOD;
        
        spr = m1.spr;
        zad = m2.zad;
        
        for (int i = m1.beg.size()+1; i < p.size() && i <= beg.size(); ++i) {
            if (p.substr(lp-i, i) == beg.substr(0, i)) {
                spr.push_back(i);
            }
        }
        for (int i = m2.end.size()+1; i < p.size() && i <= end.size(); ++i) {
            if (p.substr(0, i) == end.substr(end.size()-i, i)) {
                zad.push_back(i);
            }
        }
    }
};

ostream& operator<<(ostream& os, Mute m) {
    os << "beg = " << m.beg << '\n';
    os << "end = " << m.end << '\n';
    os << "cnt = " << m.cnt << '\n';
    os << "spr: ";
    for (int x : m.spr) {
        os << x << ' ';
    }
    os << "\nzad: ";
    for (int x : m.zad) {
        os << x << ' ';
    }
    return os << '\n';
}

int main() {
    string s1, s2;
    cin >> p >> s1 >> s2;
    lp = p.size();
    
    vector<Mute> mutes;
    mutes.push_back(Mute(s1, s1));
    mutes.push_back(Mute(s2, s2));
    
    int n, a ,b;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        mutes.emplace_back(mutes[a-1], mutes[b-1]);
    }
    
    //mutes.push_back(Mute(mutes[0], mutes[1]));

//     for (Mute m : mutes) {
//         cout << m << endl;
//     }
    cout << mutes.back().cnt << endl;
    
    
    return 0;
}