Create a TRIE data structure using C++ which can handle text. The user will ente
ID: 3695535 • Letter: C
Question
Create a TRIE data structure using C++ which can handle text. The user will enter a string. After you build the trie, allow the user to search a single word and determine whether or not it was in the original text. You should provide 4 functions: (1) receive the text and build the trie; (2) receive a word and determine whether it exists within the text. OUTPUT: Found or NOT found (3) Identify at what position within the text the word appears. (4) Be able to cope with the same text found multiple times.
Explanation / Answer
#include<iostream>
#include<vector>
#define MAX_CHAR 256
using namespace std;
// A Suffix Trie (A Trie of all suffixes) Node
class SuffixTrieNode
{
private:
SuffixTrieNode *children[MAX_CHAR];
vector<int> indexes;
public:
SuffixTrieNode() // Constructor
{
for (int i = 0; i < MAX_CHAR; i++)
children[i] = nullptr;
}
void insertSuffix(string s, int index)
{
if(s.size()==0) return;
char cIndex=s[0];
if(children[cIndex]==nullptr)
children[cIndex]=new SuffixTrieNode();
children[cIndex]->insertSuffix(s.substr(1), index);
children[cIndex]->indexes.push_back(index);
}
vector<int> search(string s)
{
if(s.size()==0) return indexes;
if(children[s[0]]) return children[s[0]]->search(s.substr(1));
else return vector<int>();
}
};
// A Trie of all suffixes
class SuffixTrie
{
private:
SuffixTrieNode root;
public:
SuffixTrie(vector<string>& vec)
{
for(int i=0; i<vec.size(); i++)
insert(vec[i], i);
}
void insert(string& txt, int i)
{
for(int index=0; index<txt.size(); index++)
root.insertSuffix(txt.substr(index), i);
}
void search(string pat)
{
vector<int> result = root.search(pat);
if(result.size()==0)
cout << "Word not found" << endl;
else
{
for(int i=0; i<result.size(); i++)
cout << "Word found at position " << result[i] << endl;
}
}
};
// driver program to test above functions
int main()
{
vector<string> vec={"there","is","an","answer","to","their","question","in","their","quiz","the","third","largest","question"};
SuffixTrie trie(vec);
cout<<"search for word "es":"<<endl;
trie.search("es");
cout<<"search for word "the":"<<endl;
trie.search("the");
cout<<"search for word "their":"<<endl;
trie.search("their");
cout<<"search for word "theer":"<<endl;
trie.search("theer");
cout<<"search for word "th":"<<endl;
trie.search("th");
return 0;
}
sample output
search for word "the":
Word found at position 0
Word found at position 5
Word found at position 8
Word found at position 10
search for word "their":
Word found at position 5
Word found at position 8
search for word "theer":
Word not found
search for word "th":
Word found at position 0
Word found at position 5
Word found at position 8
Word found at position 10
Word found at position 11