Cod sursa(job #2831710)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 11 ianuarie 2022 21:51:34
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>

std::ifstream f("abc2.in");
std::ofstream g("abc2.out");

char s[10000001], word[21];
char ch;

int len, k, sol;

struct Trie {
    int cnt, nrfii;
    Trie *arr[3];
 
    Trie() {
        cnt = nrfii = 0;
        for(int i = 0;i < 3;i++)
            arr[i] = 0;
    }
};
    
Trie *T = new Trie;
 
void insrt(Trie *root, char *str) {
    if(*str == '\0') {
        root -> cnt = 1;
        return;
    }
 
    if(root -> arr[(*str) - 'a'] == 0) {
        root -> arr[(*str) - 'a'] = new Trie;
        root -> nrfii++;
    }
 
    insrt(root -> arr[(*str) - 'a'], str + 1);
}

    
int que(Trie *root, char *str) {
    if(*str == '\0')
        return root -> cnt;
 
    if(root -> arr[(*str) - 'a'])
        return que(root -> arr[(*str) - 'a'], str + 1);
 
    return 0;
}

void solve() {
    f >> s;
    while(!f.fail()) {
        f >> word;
        insrt(T, word);
    }

    len = strlen(s), k = strlen(word);
    for(int i = 0;i < len - k + 1;i++) {
        ch = s[i + k];
        s[i + k] = '\0';
        sol += que(T, s + i);
        s[i + k] = ch;
    }

    g << sol;
}

int main() {

    int T = 1;
    for(;T;T--) {
        solve();
    }

    return 0;
}