C++ Programming Code Examples C++ > Strings Code Examples C++ Program to Implement Longest Prefix Matching C++ Program to Implement Longest Prefix Matching This C++ Program demonstrates the implementation of Longest Prefix Matching. #include<iostream> #include<cstdlib> #include<cstring> #include<stack> using namespace std; /* node Declaration */ struct node { char data; node *child[128]; node() { for (int i = 0; i < 128; i++) child[i] = NULL; } }; /* trie class Declaration */ 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 add(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']; } } void check(node *cur, string S, int i) { if (cur) { cout<<cur->data; if (i < S.length()) check(cur->child[S[i] - 'A'], S, i + 1); } } void checkroot(string S) { if (root && S.length() > 0 && S[0] > 'A') check(root->child[S[0] - 'A'],S,1); else cout<<"\nEmpty root \n"; } }; /* Main */ int main() { trie dict; dict.add("are"); dict.add("area"); dict.add("base"); dict.add("cat"); dict.add("cater"); dict.add("basement"); string input; input = "caterer"; cout<<input << ": "; dict.checkroot(input); cout<<endl; input = "basement"; cout<<input << ": "; dict.checkroot(input); cout<<endl; input = "are"; cout<<input << ": "; dict.checkroot(input); cout<<endl; input = "arex"; cout<<input << ": "; dict.checkroot(input); cout<<endl; input = "basemexz"; cout<<input << ": "; dict.checkroot(input); cout<<endl; input = "xyz"; cout<<input << ": "; dict.checkroot(input); cout<<endl; return 0; }