Cod sursa(job #1005041)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 octombrie 2013 22:56:26
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>

#include <cstring>
using namespace std;

const int MAX_L = 105;
const int SIGMA = 26;

struct Trie {
    int a, b, l;
    Trie *sons[SIGMA];

    Trie() {
        for(int i = 0; i < SIGMA; ++i)
            sons[i] = NULL;
        a = b = l = 0;
    }
};

int Na, Nb, sol;
char S[MAX_L], A[MAX_L];
Trie *root = new Trie;

inline void insert(Trie *node, char S[], int beg, int end, char M, int ind) {
    for(int i = beg; i <= end; ++i) {
        int next = S[i] - 'a';
        if(node->sons[next] == NULL)
            node->sons[next] = new Trie;
        node = node->sons[next];
        if(node->l != ind) {
        node->l = ind;
        if(M == 'A')
            ++node->a;
        else ++node->b;
        }
    }
}

inline void DFS(Trie *node) {
    if(node->a == Na && node->b == 0)
        ++sol;
    for(int i = 0; i < SIGMA; ++i)
        if(node->sons[i] != NULL)
            DFS(node->sons[i]);
}

int main() {
    ifstream f("sub.in");
    ofstream g("sub.out");

    f >> Na;
    for(int q = 1; q <= Na; ++q) {
        f >> S;
        int len = strlen(S);
        if(S[len-1] == '\n')
            --len;
        for(int i = 0; i < len; ++i)
            insert(root, S, i, len-1, 'A', q);
    }
    f >> Nb;
    for(int q = 1; q <= Nb; ++q) {
        f >> S;
        int len = strlen(S);
        if(S[len-1] == '\n')
            --len;
        for(int i = 0; i < len; ++i)
            insert(root, S, i, len-1, 'B', -q);
    }
    DFS(root);

    g << sol << "\n";

    f.close();
    g.close();

    return 0;
}