gistfile1.cpp

//
//  main.cpp
//  Trie
//
//  Created by Luka Dodelia on 5/23/12.
//  Copyright (c) 2012 All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#define NODESIZE 26
using namespace std;
class LDNode
{
public:
    char c;
    bool end;
    int prefCount;
    vector<LDNode> childs;
    
    LDNode()
    {
        c = '\0';
        end = false;
        prefCount = 0;
    }
};

class LDTrie
{
    vector<LDNode> root;
    
public:
    
    LDTrie()
    {
        root.resize(NODESIZE);
    }
    
    void insert(string word)
    {
        if(word == "") return;
        int i = 0;
        insert(root[tolower(word[i]) - 'a'],word, i);
    }
    
    LDNode insert(LDNode & node,string & word,int & i)
    {
        node.c = word[i];
        node.prefCount++;
        if(i + 1 == word.length())
        {
            node.end = true;
            return node;
        }
        
        if(node.childs.size() < NODESIZE)
            node.childs.resize(NODESIZE);
        
        i++;//Magic Increment
        
        node.childs[tolower(word[i]) - 'a'] = insert(node.childs[tolower(word[i]) - 'a'],word, i);
        return node;
    }
    
    int prefCount(string word)
    {
        if(word == "") return 0;
        int i = 0,prefCount = 0;
        isTheare(root[tolower(word[i]) - 'a'], word, i,prefCount);
        return prefCount;
    }
    
    bool isTheare(string word)
    {
        if(word == "") return 0;
        int i = 0,prefCount = 0;
        return isTheare(root[tolower(word[i]) - 'a'], word, i,prefCount);
    }
    
    bool isTheare(LDNode node,string word,int & i,int & prefCount)
    {
        if(node.c != word[i])
            return false;
        
        if(i + 1 == word.length())
        {
            prefCount = node.prefCount;
            return node.end;
        }
        
        i++;//Magic Increment
        
        if(node.childs.empty())
            return false;
            
        return isTheare(node.childs[tolower(word[i]) - 'a'], word, i,prefCount);
    }
};


int main(int argc, const char * argv[])
{
    LDTrie trie;
    fstream in ("suggestions.in");
    fstream out("suggestions.out");
    int words = 0,chars = 0;
    in>>words;
    for (int i = 0; i < words; i++)
    {
        string a;
        in>>a;
        trie.insert(a);
    }
    
    in>>chars;
    string b = "";
    for (int i = 0; i < chars; i++)
    {
        char c;
        in>>c;
        if(c == '<')
            b = b.substr(0,b.size() - 1);
        else
            b += c;
        if(b.size() > 2)
            out<<trie.prefCount(b)<<"\n";
    }
    
    return 0;
}