Cod sursa(job #334613)

Utilizator levap1506Gutu Pavel levap1506 Data 27 iulie 2009 14:27:07
Problema Trie Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <string>
#include <iostream>
#define TC s[c]-'a'
using namespace std;
struct Trie {
    int fin,nrf;
    Trie *fii[26];
  Trie() {  //constructor
      fin = nrf =0;
      memset(fii,0,sizeof(fii));
  }

} *T=new Trie;
int op,i,j,k,l;
string s;
void insert(Trie *T, int c) {
    if (c==l) {
        T->fin++;
        return;
    }
    if (T->fii[TC]==0) { T->fii[TC]=new Trie; T->nrf++; }
    insert(T->fii[TC],c+1);
}
int dellete(Trie *T2, int c) {
    if (c==l) T2->fin--;
    else
    if (dellete(T2->fii[TC],c+1)) {
        T2->fii[TC]=0;
        T2->nrf--;
    }
    if (T2->nrf==0 && T2->fin==0 && T2!=T) {
        delete T2;
        return 1;
    }
    return 0;

}
int seak(Trie *T,int c) {
    if (c==l) return T->fin;
    if (T->fii[TC]) return seak(T->fii[TC],c+1);
    return 0;
}
int prefix(Trie *T, int c) {
    if (c==l) return 0;
    if (T->nrf>0&&T->fii[TC]!=0) return 1+prefix(T->fii[TC],c+1);
    return 0;
}
int main() {
    ifstream in;
    ofstream out;
    in.open("trie.in");
    out.open("trie.out");
    while (!in.eof())
    {
        in >> op >> s;
        if (in.eof()) break;
        l=s.length();
        switch (op) {
            case 0: insert(T,0);
            break;
            case 1: dellete(T,0);
            break;
            case 2: out << seak(T,0) << "\n";
            break;
            case 3: out << prefix(T,0) << "\n";
            break;
        }
    }

    return 0;
}