//Solve the Longest Prefix Matching problem: Given a dictionary of words and an

Question

//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 in Trie Class

#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;
}

Explanation / Answer

It is very Difficult to debug your program and code further.
Another implementation is provided as below.

CODE:

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>

using namespace std;

struct node
{
char data;
node *child[128];
node()
{
for (int i = 0; i < 128; i++)
child[i] = NULL;
}
};

// Trie class
class trie
{
private:
node *root;
public:
trie()
{
root = new_node(0);
}

node *new_node(int data)
{   
node *Q = new node;
Q->data = data;
return Q;
}

void longestMatchUtil(node *cur, string S, int i)
{
if (cur)
{
cout<<cur->data;
if (i < S.length())
longestMatchUtil(cur->child[S[i] - 'A'], S, i + 1);
}
}

void longestMatch(string S)
{
if (root && S.length() > 0 && S[0] > 'A')
longestMatchUtil(root->child[S[0] - 'A'],S,1);
else
cout<<" Empty root ";
}
      
       void insert(string S)
{
node *cur = root;
for (int i = 0; i < S.length(); i++)
{
if (!cur->child[S[i] - 'A'])
cur->child[S[i] - 'A'] = new_node(S[i]);
cur = cur->child[S[i] - 'A'];
}
}
};

int main()
{
trie dict;
  
dict.insert("cat");
dict.insert("cater");   
dict.insert("basement");
   dict.insert("are");
dict.insert("area");
dict.insert("base");
string input;
input = "caterer";
cout<<"input: " << input << endl;
cout << "Longest String is: " << dict.longestMatch(input) ;
cout<<endl << endl;
return 0;
}

$ g++ longest.cpp
$ a.out

input:caterer   
Longest String is: cater

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.