Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 1,930 MiB 0,000 s OK
#2 5/5 2,313 MiB 0,000 s OK
#3 5/5 2,656 MiB 0,005 s OK
#4 5/5 3,078 MiB 0,005 s OK
#5 5/5 3,461 MiB 0,005 s OK
#6 5/5 5,516 MiB 0,005 s OK
#7 5/5 5,516 MiB 0,005 s OK
#8 5/5 5,477 MiB 0,005 s OK
#9 6/6 5,375 MiB 0,011 s OK
#10 6/6 5,484 MiB 0,029 s OK
#11 6/6 1,520 MiB 0,000 s OK
#12 6/6 1,543 MiB 0,000 s OK
#13 6/6 1,520 MiB 0,000 s OK
#14 6/6 1,535 MiB 0,000 s OK
#15 6/6 1,586 MiB 0,000 s OK
#16 6/6 1,563 MiB 0,000 s OK
#17 6/6 1,551 MiB 0,000 s OK
#18 6/6 5,484 MiB 0,029 s OK

Ocenjevani program (pasavci.cpp):
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL;
const int L = 2000;
const int M = 2000;

char P[L];
int b[L], lenP;
void kmpPreprocess(){
    int i = 0, j = -1; b[0] = -1;
    while(i < lenP){
        while(j>=0 && P[i] != P[j]) j = b[j];
        i++; j++;
        b[i] = j;
    }
}

struct Pasavec{
    char pref[L];
    char suff[L];
    int prefLen;
    int suffLen;
    ll pCount;
};

Pasavec pas[M];
char s1[L], s2[L];
char currMerge[L + L + L];

ll kmpCount(char* T, int len){
    int i = 0, j = 0;
    ll count = 0;
    while(i < len){
        while(j >= 0 && T[i] != P[j])
            j = b[j];
        i++; j++;
        if(j == lenP){
            count++;
            j = b[j];
        }
    }
    return count;
}

int main(){
    int m;
    scanf("%s",P);
    lenP = strlen(P);
    kmpPreprocess();
    
    scanf("%s",s1);
    scanf("%s",s2);
    scanf("%d",&m);
    
    int lenS1 = strlen(s1);
    int lenS2 = strlen(s2);
    
    //printf("Input ok\n");
    pas[0].pCount = kmpCount(s1, lenS1);
    pas[0].prefLen = min(lenS1, lenP - 1);
    pas[0].suffLen = min(lenS1, lenP - 1);
    if(pas[0].prefLen > 0)
        for(int i = 0;i < pas[0].prefLen;i++)
            pas[0].pref[i] = s1[i];
    if(pas[0].suffLen > 0)
        for(int i = lenS1 - 1;i >= lenS1 - pas[0].suffLen;i--)
            pas[0].suff[i - (lenS1 - pas[0].suffLen)] = s1[i];
    
    pas[1].pCount = kmpCount(s2, lenS2);
    pas[1].prefLen = min(lenS2, lenP - 1);
    pas[1].suffLen = min(lenS2, lenP - 1);
    if(pas[1].prefLen > 0)
        for(int i = 0;i < pas[1].prefLen;i++)
            pas[1].pref[i] = s2[i];
    if(pas[1].suffLen > 0)
        for(int i = lenS2 - 1;i >= lenS2 - pas[1].suffLen;i--)
            pas[1].suff[i - (lenS2 - pas[1].suffLen)] = s2[i];
      
    // zdruzi
    for(int k = 0;k < m;k++){
        int ak, bk;
        scanf("%d %d",&ak,&bk);
        ak--; bk--;
        
       // printf("merge %d\n",k);
       // printf("calculate pcount\n");
        int mergeLen = 0;
        for(int i = 0; i < pas[ak].suffLen;i++)
            currMerge[mergeLen++] = pas[ak].suff[i];
        for(int i = 0;i < pas[bk].prefLen;i++)
            currMerge[mergeLen++] = pas[bk].pref[i];
        pas[k+2].pCount = (pas[ak].pCount + pas[bk].pCount + kmpCount(currMerge,mergeLen)) % MOD;
      //  printf("pcount finished!\n");
        
        // construct prefix
        pas[k+2].prefLen = 0;
        for(int i = 0; i < pas[ak].prefLen;i++)
            pas[k+2].pref[pas[k+2].prefLen++] = pas[ak].pref[i];
        for(int i = 0; i < pas[bk].prefLen && (pas[k+2].prefLen < lenP - 1);i++)
            pas[k+2].pref[pas[k+2].prefLen++] = pas[bk].pref[i];
        
        // construct suffix
        pas[k+2].suffLen = 0;
        if(pas[bk].suffLen == lenP - 1){
            for(int i = 0; i < pas[bk].suffLen;i++)
                pas[k+2].suff[i] = pas[bk].suff[i];
            pas[k+2].suffLen = lenP - 1;
        }
        else{
            int maxLen = min(lenP - 1, pas[bk].suffLen + pas[ak].suffLen);
            pas[k+2].suffLen = maxLen;
            for(int i = pas[bk].suffLen - 1;i >= 0;i--)
                pas[k+2].suff[--maxLen] = pas[bk].suff[i];
            for(int i = pas[ak].suffLen - 1; i >= 0 && maxLen > 0;i--)
                pas[k+2].suff[--maxLen] = pas[ak].suff[i];
            
        }
    }
    printf("%lld\n", pas[m+1].pCount);
    
    return 0;
}