//Solve the Longest Prefix Matching problem: Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.

For example, assume the dictionary contains words he and hello, then the longest prefix of hello is he, and the longest prefix of he is empty (or an empty string).

This program is complete only needs to implement The longestprefix function

#ifndef TRIE_H

#define TRIE_H

#include

using namespace std;

#define MAX_CHAR 256

class Node { private: Node *children[MAX_CHAR]; bool bisEnd; public: Node(); bool isEnd(); void insert(string suffix); Node* search(string pat); };

class Trie { private: Node root; public: void add(string word); bool contains(string pat); bool isPrefix(string pat);

string longestPrefix(string word);

};

#endif

============================================

#ifndef TRIE_CPP #define TRIE_CPP

#include #include #include "trie.h"

using namespace std;

Node::Node() { for (int i = 0; i < MAX_CHAR; i++) // initialize NULL to all child in constructor children[i] = NULL; bisEnd = false; } bool Node::isEnd() {return bisEnd == true;} void Node::insert(string suffix) { Node *temp = this; for (int i = 0; i < suffix.size(); i++) { if (!temp->children[suffix[i]]) // if char is not found temp->children[suffix[i]] = new Node(); // add new node to this child temp = temp->children[suffix[i]]; // update temp to next child node } temp->bisEnd = true; }

Node* Node::search(string pat) { Node *temp = this; for (int i = 0; i < pat.size(); i++) { if (!temp->children[pat[i]]) return NULL; // if char is not found pat doesnot exist temp = temp->children[pat[i]];// update temp to next child node } return temp; // this pattern exist }

bool Trie::contains(string pat) { Node *node = root.search(pat); // search for pattern if (node && node->isEnd()) return true; // if pattern is found and bisEnd is set this word exist return false; }

bool Trie::isPrefix(string pat) { Node *node = root.search(pat); // search for pattern if (node) return true; // if pattern is found return true return false; }

void Trie::add(string word) { root.insert(word); // insert word to root } #endif

=========================================

#include #include "trie.h"

using namespace std;

int main() { Trie vocabulary; cout << "Type a word ('q' for quit): "; string word; cin >> word; while(word != "q") { vocabulary.add(word); cout << "The longest prefix is: " << vocabulary.longestPrefix(word) << endl; cout << "Type a word ('q' for quit): "; cin >> word; } return 0; }