Category Archives: Trie

(LightOj) 1129 – Consistency Checker

0
Posted on by 

/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here


int N;
string str;

bool isPossible;

struct DATA {
    bool endHere;
    bool hasTrace;
    DATA *child[10];

    DATA()
    {
        endHere = false;
        hasTrace = false;
        loop(i, 10) child[i] = NULL;
    }
    ~DATA()
    {
        loop(i, 10)
        {
            if(child[i] != NULL)
                delete child[i];
        }
    }
};

void addString(string &str, DATA *curNode)
{
    if(!isPossible) return;

    loop(i, SZ(str))
    {
        curNode->hasTrace = true;

        str[i] = str[i] - '0';
        if(curNode->child[ str[i] ] == NULL)
            curNode->child[ str[i] ] = new DATA();
        curNode = curNode->child[ str[i] ];


        if(curNode->endHere)
        {
            isPossible = false;
            return;
        }
    }

    if(curNode->hasTrace)
        isPossible = false;

    curNode->endHere = true;
}



void init()
{

}




int main()
{


    init();

    int kases, kaseno = 0;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d", &N);

        DATA *head = new DATA();

        isPossible = true;

        loop(i, N)
        {
            cin>>str;
            addString(str, head);
            //dump(head);
        }

        delete head;
        if(isPossible)
        {
            pf("Case %d: YES\n", ++kaseno);
        }
        else
        {
            pf("Case %d: NO\n", ++kaseno);
        }
    }



    return 0;
}

(UVa) 615 – Is It A Tree?

0
Posted on by 

/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here







set<int>NodeList;

set<int>inputNodes;

map<int,int>parent;


int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}



void init()
{

}


int main()
{
    init();

    int kaseno = 0;
    int p, q;
    int edge;
    bool possible;

    while(true)
    {
        scanf("%d %d", &p, &q);
        if(p < 0 && q < 0)
        {
            break;
        }
        else
        {
            edge = 0;
            NodeList.clear();
            inputNodes.clear();
            parent.clear();
            possible = true;

            while(p != 0 && q != 0)
            {
                edge++;
                NodeList.insert(p);
                NodeList.insert(q);

                if(parent[p] == 0)
                {
                    parent[p] = p;
                }

                if(parent[q] == 0)
                {
                    parent[q] = q;
                }

                int u = find(p);
                int v = find(q);
                if(u == v)
                {
                    possible = false;
                }

                parent[ v ] = u;

                if(inputNodes.find(q) != inputNodes.end())
                {
                    possible = false;
                }
                else
                {
                    inputNodes.insert(q);
                }

                scanf("%d %d", &p, &q);
            }

            if( edge == 0 || (possible && (edge == SZ(NodeList) - 1) && (edge == SZ(inputNodes)) ) )
            {
                pf("Case %d is a tree.\n", ++kaseno);
            }
            else
            {
                pf("Case %d is not a tree.\n", ++kaseno);
            }

        }
    }



    return 0;
}

(USACO) Longest Prefix

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?a=QX6ufTaKJ4D&S=prefix

/*
ID: himuhas1
TASK: prefix
LANG: C++
*/

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<stdio.h>

#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<utility>

#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define all(v) v.begin(), v.end()
#define pb push_back
#define sf scanf
#define pf printf
#define mem(a, v) memset(a, v, sizeof(a))
#define dd double
#define ll long long
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())

using namespace std;


#define NO_CHILD -2
#define NO_MAP -1

#define MAXX 200002

struct Trie{
    map<int, map<int, int> > childNode;
    vector<bool>allNodes;
    int id;
    int *p;
    int zero;


    Trie()
    {
        allNodes.pb(0);
        zero = 0;
    }


    void add(const string &val)
    {
        p = &zero;
        int ch;
        loop(i, SZ(val))
        {
            ch = val[i];
            p = &childNode[*p][ch];
            if(*p == 0)
            {
                *p = SZ(allNodes);
                allNodes.pb(0);
            }
        }

        allNodes[*p] = 1;
    }

    void iniCharByCharSearch()
    {
        id = 0;
    }

    int charByCharSearch(char ch)
    {
        if(childNode[id].find(ch) == childNode[id].end())
        {
            return NO_CHILD;
        }
        else
        {
            id = childNode[id][ch];
            return allNodes[id];
        }
    }
};






int main()
{
    #ifndef hasibpc
        freopen("prefix.in", "r", stdin);
        freopen("prefix.out", "w", stdout);
    #endif // hasibpc

    Trie tr;

    string name;
    string str;
    while(1)
    {
        cin>>name;
        if(name[0] == '.') break;

        tr.add(name);
    }

    while(cin>>name)
    {
        str += name;
    }

    bool dp[MAXX];
    mem(dp, 0);
    int ret;
    int result = 0;
    //dp[0] = 1;
    for(int i=-1; i<SZ(str); i++)
    {
        if(i==-1 || dp[i])
        {
            result = max(result, i+1);
            tr.iniCharByCharSearch();
            FOR(j, i+1, SZ(str))
            {
                ret = tr.charByCharSearch(str[j]);

                //pf("%d %d ==> %d\n", i, j, ret);

                if(ret == 1)
                {
                    //cout<<"j = "<< j<<endl;

                    dp[j] = 1;
                    //result = max(result, j+1);
                }


                if(ret == NO_CHILD)
                    break;

            }
        }
    }

    cout<<result<<endl;




    return 0;
}

(UVa) 10226 – Hardwood Species

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1167
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)

using namespace std;


#define ALPHA_LIST 128

struct node{
    int cnt_trees;
    node *child[ALPHA_LIST];

    node()
    {
        cnt_trees = 0;
        loop(i, ALPHA_LIST)
        {
            child[i] = NULL;
        }
    }
}*head;

int total;


/*
void clearTree(node *p)
{
    loop(i, ALPHA_LIST)
    {
        if(p->child[i] != NULL)
        {
            clearTree(p->child[i]);
        }
    }
    delete p;
}

void init()
{
    head = new node();
}


int toint(char c)
{
    if(c== ' ')
        return 26;
    if('a' <= c && c <= 'z')
        return c - 'a';
    else
        return c - 'A';
}
*/

void insert(char *word)
{
    //cout<<"inserting " << word<<endl;
    node *current = head;

    int ch;

    while(*word != '\0')
    {
        ch = *word;

        if(current->child[ch] == NULL)
            current->child[ch] = new node();
        current = current->child[ch];
        word++;
    }
    current->cnt_trees++;
}

vector<char> name_list;

void printTree(node *current)
{
    if(current->cnt_trees)
    {
        FOR(i, 0, SZ(name_list))
        {
            pf("%c", name_list[i]);
        }
        pf(" %.4lf\n", (100.0*current->cnt_trees)/(double)total);
        //current->cnt_trees = 0;
    }

    loop(i, ALPHA_LIST)
    {
        if(current->child[i] != NULL)
        {
            name_list.pb(i);
            printTree(current->child[i]);
            name_list.pop_back();
        }
    }

    delete current;
    //current = NULL;
}


int main()
{
    int kases;
    char names[35];
    bool blank = 0;

    gi(kases);
    cin.ignore();
    cin.ignore();

    while(kases--)
    {
        if(blank) pf("\n");
        blank = 1;

        head = new node();

        //init();

        //cout<<head<<endl;

        total = 0;
        while(gets(names))
        {
            if(strlen(names) == 0) break;
            insert(names);
            total++;
        }

        printTree(head);

        //head = NULL;
        //cout<<head<<endl<<endl<<endl;

        //clearTree(head);
    }


    return 0;
}