spell-check-1.cpp

#include <iostream>
#include <fstream>
#include <cctype>
using namespace std;

class Trie
{
  public:
    struct Node
    {
      Node() : final(false)
      {
        for(int i = 0;i < 26;++i)
          children[i] = 0;
      }

      ~Node()
      {
        for(int i = 0;i < 26;++i)
          if(children[i]) delete children[i];
      }

      Node*& child(char c)
      {
        return children[tolower(c)-'a'];
      }

      Node* children[26];
      bool final;
    };

    Trie()
    {
      root = new Node;
    }

    ~Trie()
    {
      delete root;
    }

    void add(string word)
    {
      Node* curr = root;
      for(int i = 0;i < word.length();++i)
      {
        char& c = word[i];
        if(!isalpha(c)) continue;
        if(!curr->child(c))
          curr->child(c) = new Node;
        curr = curr->child(c);
      }
      curr->final = true;
    }

    bool search(string word)
    {
      Node* curr = root;
      for(int i = 0;i < word.size();++i)
      {
        char& c = word[i];
        if(!isalpha(c)) continue;
        if(!curr->child(c)) return false;
        curr = curr->child(c);
      }
      return curr->final;
    }
  private:
    Node* root;
};

int main()
{
  Trie trie;
  string tmp;
  
  cout << "indexing dictionary...";
  ifstream dict("/usr/share/dict/words");
  while(!dict.eof())
  {
    dict >> tmp;
    trie.add(tmp);
  }
  cout << " done" << endl;

  for(;;)
  {
    cout << "> ";
    cin >> tmp;
    if(tmp == "add")
    {
      cin >> tmp;
      trie.add(tmp);
      cout << "added \"" << tmp << "\"";
    }
    else if(tmp == "search")
    {
      cin >> tmp;
      cout << trie.search(tmp);
    }
    else
      cerr << "unrecognized command";
    cout << endl;
  }
}