Cod sursa(job #2605725)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 25 aprilie 2020 18:18:23
Problema Trie Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <stdio.h>
#include <stdlib.h>

int n, m;

typedef struct TrieStruct{
    int wordsContained;
    int lastWord;
    struct TrieStruct *next[27];
}Trie;

void add_trie(Trie *crtNode, char *word, int wordIndex, int type){
    if(crtNode->lastWord != wordIndex){
        crtNode->wordsContained ++;
        crtNode->lastWord = wordIndex;
    }
    if(*word == 0){
        return;
    }
    int nextIndex = *word - 'a';
    if(crtNode->next[nextIndex] == NULL){
        if(type == 0)
            crtNode->next[nextIndex] = calloc(1, sizeof(Trie));
        else
            return;
    }
    add_trie(crtNode->next[nextIndex], word + 1, wordIndex, type);
}

void reset(Trie *crtNode, char *word){
    crtNode->wordsContained = 0;
     if(*word == 0){
        return;
    }
    int nextIndex = *word - 'a';
    if(crtNode->next[nextIndex] != NULL)
        reset(crtNode->next[nextIndex], word + 1);
}

int dfs(Trie *crtNode){
    int sum = 0;
    for(int i = 0; i < 27; ++ i){
        if(crtNode->next[i] != NULL){
            if(crtNode->next[i]->wordsContained == n)
                sum = sum + 1 + dfs(crtNode->next[i]);
            else
                sum = sum + dfs(crtNode->next[i]);
        }
    }
    return sum;
}

int main()
{
    FILE *in = fopen("sub.in", "r");
    FILE *out = fopen("sub.out", "w");
    Trie *trie = calloc(1, sizeof(Trie));

    char word[400] = {};
    fscanf(in, "%d", &n);
    for(int i = 1; i <= n; ++ i){
        fscanf(in, "%s", &word);
        int cnt = 0;
        while(word[cnt] != 0){
            if(i == 1)
                add_trie(trie, word + cnt, i, 0);
            else
                add_trie(trie, word + cnt, i, 1);
            cnt ++;
        }
    }

    fscanf(in, "%d", &m);

    for(int i = 1; i <= m; ++ i){
        fscanf(in, "%s", &word);
        int cnt = 0;
        while(word[cnt] != 0){
            reset(trie, word + cnt);
            cnt ++;
        }
    }

    fprintf(out, "%d", dfs(trie));

    return 0;
}