Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,133 MiB 0,004 s OK
#2 5/5 3,168 MiB 0,004 s OK
#3 5/5 3,172 MiB 0,004 s OK
#4 5/5 3,156 MiB 0,004 s OK
#5 5/5 3,156 MiB 0,004 s OK
#6 5/5 3,203 MiB 0,004 s OK
#7 5/5 3,191 MiB 0,004 s OK
#8 5/5 3,219 MiB 0,004 s OK
#9 6/6 3,223 MiB 0,004 s OK
#10 6/6 5,129 MiB 0,021 s OK
#11 6/6 3,117 MiB 0,004 s OK
#12 6/6 3,148 MiB 0,004 s OK
#13 6/6 3,145 MiB 0,004 s OK
#14 6/6 3,148 MiB 0,004 s OK
#15 6/6 3,129 MiB 0,004 s OK
#16 6/6 3,148 MiB 0,004 s OK
#17 6/6 3,125 MiB 0,004 s OK
#18 6/6 5,152 MiB 0,021 s OK

Ocenjevani program (Pasavci.cpp):
//
//  Pasavci.cpp
//  UPM-2.kolo
//
//  Created by Urban Duh on 11/05/2017.
//  Copyright Š 2017 Urban Duh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
using namespace std;

struct item{
    string frst;
    string lst;
    int num;
    //string whl;
};

int b[1000];

int KMP (string T, string P){
    int count = 0;
    int n = (int)T.length(), m = (int)P.length();
    
    //Search
    int i = 0;
    int j = 0;
    
    while (i < n){
        while (j >= 0 && T[i] != P[j]) j = b[j];
        i++;
        j++;
        if (j == m){
            count++; //match starting at i-j
            j = b[j];
        }
    }
    
    return count;
}

int main (){
    string p, s1, s2;
    int m, x, y, mod = 1000000007;
    cin>>p>>s1>>s2>>m;
    int l = (int) p.length() - 1;
    item *items = new item[m+2];
    
    //KMP preprocess
    {
    b[0] = -1;
    int i = 0, j = -1;
    
    while (i < m){
        while (j >= 0 && p[i] != p[j]) j = b[j];
        i++;
        j++;
        b[i] = j;
    }
    }
    
    items[0].num = KMP(s1, p);
    items[1].num = KMP(s2, p);
    items[0].frst = s1.length() >= l ? s1.substr(0, l) : s1;
    items[0].lst = s1.length() >= l ? s1.substr(s1.length()-l, l) : s1;
    items[1].frst = s2.length() >= l ? s2.substr(0, l) : s2;
    items[1].lst = s2.length() >= l ? s2.substr(s2.length()-l, l) : s2;
    
    for (int i = 2; i < m+2; i++){
        cin>>x>>y;
        x--; y--;
        items[i].num = (items[x].num + items[y].num) % mod;
        items[i].num = (items[i].num + KMP(items[x].lst + items[y].frst, p)) % mod;
        
        if (items[x].frst.length() == l) items[i].frst = items[x].frst;
        else{
            string s = items[x].frst + items[y].frst;
            items[i].frst = s.length() >= l ? s.substr(0, l) : s;
        }
        if (items[y].lst.length() == l) items[i].lst = items[y].lst;
        else{
            string s = items[x].lst + items[y].lst;
            items[i].lst = s.length() >= l ? s.substr(s.length()-l, l) : s;
        }
        
        //items[i].whl = items[x].whl + items[y].whl;
    }
    
    /*for (int i = 0; i < m+2; i++){
        cout<<items[i].frst<<" "<<items[i].lst<<" "<<items[i].num<<endl;
    }*/
    
    cout<<items[m+1].num;
}