Cod sursa(job #1330639)

Utilizator ooptNemes Alin oopt Data 30 ianuarie 2015 20:32:46
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
/// sub
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <string>
#define ch(a) ((int)((a)-'a'))
using namespace std;

struct trie {
    trie *son[26];
    int last;
    int cnt;
    bool valid;
    trie() {
        cnt = 0;
        last = 0;
        valid = true;
        for (int i=0;i<26;i++) {
            son[i] = NULL;
        }
    }
    ~trie() {
        cnt = 0;
        last = 0;
        valid = false;
        for (int i=0;i<26;i++) {
            delete son[i];
            son[i] = NULL;
        }
    }
};

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

struct trie *root, *node;
int n, m;
string in;
int len;

void addTrieA(int index) {
    for (int i=0;i<len;i++) {
        node = root;
        for (int j=i;j<len;j++) {
            int p = ch(in[j]);
            if (node->son[p] == NULL)
                node->son[p] = new trie();
            if (node->son[p]->valid)
                node = node->son[p];
            else
                break;
            if (node->last < index) {
                node->last = index;
                node->cnt++;
            }
        }
    }
}

void markB() {
    for (int i=0;i<len;i++) {
        node = root;
        for (int j=i;j<len;j++) {
            int p = ch(in[j]);
            if (node->son[p] != NULL) {
                node->son[p]->valid = false;
                node = node->son[p];
            } else
                break;
        }
    }
}

int countTrie(trie *aux) {

    int answ = 0;
    if (aux->cnt == n && aux->valid) answ = 1;

    for (int i=0;i<26;i++)
        if (aux->son[i] != NULL)
            answ += countTrie(aux->son[i]);

    return answ;
}

void read() {
    root = new trie();

    f>>n;
    for (int i=1;i<=n;i++) {
        f>>in;
        len = in.size();
        addTrieA(i);
    }

    f>>m;
    for (int i=1;i<=m;i++) {
        f>>in;
        len = in.size();
        markB();
    }

    g<<countTrie(root)<<'\n';
}

int main() {

    read();

    f.close(); g.close();
    return 0;
}