Spell Check

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <fstream>
#include <sstream>
#include <algorithm>

using namespace std;

class BK{
private:
    struct Node{
        string word;
        map<int,Node*> children;
        Node(string w) : word(w){}
    };

    Node* root;
    const int threshold = 2;

    int lev(string s1, string s2){
        int m = static_cast<int>(s1.size()),
            n = static_cast<int>(s2.size());
        vector<vector<int>> c(n + 1, vector<int>(m + 1));
        for(int i = 0; i <= m; i++) c[0][i] = i;
        for(int i = 1; i <= n; i++) c[i][0] = i;
        for(int i = 1,k; i <= n; i++){
            for(int j = 1; j <= m; j++){
                k = c[i-1][j-1]+(s1[j-1]==s2[i-1]?0:1);
                c[i][j] = (c[i][j-1]<c[i-1][j]?c[i][j-1]:c[i-1][j])+1;
                c[i][j] = (c[i][j]<k)?c[i][j]:k;
            }
        }
        return c[n][m];
    }

    void clearNode(Node* root){
        if(!root->children.empty())
            for(auto i = root->children.begin(); i != root->children.end(); ++i) clearNode(i->second);
        delete root;
    }

    void insert(Node* root, string s){
        int diff = lev(root->word, s);
        if(root->children.count(diff))
            insert(root->children[diff], s);
        else
            root->children.insert({diff, new Node(s)});
    }

    void getSuggestion(Node* root, string s, vector<string>& v){
        int diff = lev(root->word, s);
        if(diff <= threshold)
            v.push_back(root->word);
        for(int i = diff-threshold; i <= diff+threshold; i++){
            if(root->children.count(i))
                getSuggestion(root->children[i], s, v);
        }
    }
public:
    BK() : root(nullptr){}
    ~BK(){
        clearNode(root);
    }

    void insert(string s){
        if(!root)
            root = new Node(s);
        else
            insert(root, s);
    }

    vector<string> getSuggestion(string s){
        vector<string> v;
        getSuggestion(root, s, v);
        return v;
    }
};

void populate(string fName, BK& b, vector<string>& v);
void parseString(string s, BK& b, vector<string>& v);
bool inDict(string s, vector<string>& v);

int main(){
    vector<string> dictionary;
    BK bkTree;
    populate("words.txt", bkTree, dictionary);

    string s;

    while(true) {
        cout << "\nEnter a string: ";
        getline(cin, s);
        parseString(s, bkTree, dictionary);
    }
}

void populate(string fName, BK& b, vector<string>& v){
    ifstream in(fName);
    string s;

    if(!in){
        cerr << "Error opening file: " << fName;
        throw string("Bad File");
    }

    cout << "Now populating dictionary and BK-Tree..." << endl;
    while(getline(in, s)){
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        v.push_back(s);
        b.insert(s);
    }
    cout << "Finished!" << endl;
}

void parseString(string s, BK& b, vector<string>& v){
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    stringstream ss(s); //snake
    vector<string> suggestions;

    while(getline(ss, s, ' ')){
        if(!inDict(s,v)){
            suggestions = b.getSuggestion(s);
            cout << "Misspelled word: " << s << endl;
            cout << "Suggestions: ";
            for(auto i = suggestions.begin(); i != suggestions.end(); ++i)
                cout << *i << " ";
            cout << endl << endl;
        }
    }
}

bool inDict(string s, vector<string>& v){
    int l = 0, h = static_cast<int>(v.size())-1, m;
    while(l <= h){
        m = (l + h) / 2;
        if(v[m] > s)
            h = m - 1;
        else if(v[m] < s)
            l = m + 1;
        else
            return true;
    }
    return false;
}