C++ Program to Implement Longest Prefix Matching

«
»
This C++ Program demonstrates the implementation of Longest Prefix Matching.

Here is source code of the C++ Program to demonstrate the implementation of Longest Prefix Matching. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C++ Program to Implement Longest Prefix Matching
  3.  */
  4. #include<iostream>
  5. #include<cstdlib>
  6. #include<cstring>
  7. #include<stack>
  8. using namespace std;
  9.  
  10. /* 
  11.  * node Declaration
  12.  */
  13. struct node
  14. { 
  15.     char data; 
  16.     node *child[128];
  17.     node()
  18.     {
  19.         for (int i = 0; i < 128; i++)
  20.             child[i] = NULL;
  21.     }
  22. };
  23.  
  24. /* 
  25.  * trie class Declaration
  26.  */
  27. class trie
  28. { 
  29.     private: 
  30.         node *root;
  31.     public: 
  32.         trie() 
  33.         { 
  34.             root = new_node(0);
  35.         }
  36.  
  37.         node *new_node(int data) 
  38.         {   
  39.             node *Q = new node; 
  40.             Q->data = data; 
  41.             return Q; 
  42.         }
  43.  
  44.         void add(string S) 
  45.         { 
  46.             node *cur = root; 
  47.             for (int i = 0; i < S.length(); i++)
  48.             {
  49.                 if (!cur->child[S[i] - 'A']) 
  50.                     cur->child[S[i] - 'A'] = new_node(S[i]);
  51.                 cur = cur->child[S[i] - 'A']; 
  52.             }
  53.         }
  54.  
  55.         void check(node *cur, string S, int i) 
  56.         { 
  57.             if (cur) 
  58.             { 
  59.                 cout<<cur->data; 
  60.                 if (i < S.length()) 
  61.                     check(cur->child[S[i] - 'A'], S, i + 1); 
  62.             }
  63.         }
  64.  
  65.         void checkroot(string S) 
  66.         { 
  67.             if (root && S.length() > 0 && S[0] > 'A') 
  68.                 check(root->child[S[0] - 'A'],S,1); 
  69.             else 
  70.                 cout<<"\nEmpty root \n"; 
  71.         }
  72. };
  73.  
  74. /* 
  75.  * Main
  76.  */
  77. int main() 
  78. { 
  79.     trie dict;
  80.     dict.add("are");
  81.     dict.add("area");
  82.     dict.add("base");
  83.     dict.add("cat");
  84.     dict.add("cater");       
  85.     dict.add("basement");
  86.     string input;
  87.     input = "caterer";
  88.     cout<<input << ":   ";
  89.     dict.checkroot(input); 
  90.     cout<<endl;
  91.     input = "basement";
  92.     cout<<input << ":   ";
  93.     dict.checkroot(input); 
  94.     cout<<endl;
  95.     input = "are";
  96.     cout<<input << ":   ";
  97.     dict.checkroot(input); 
  98.     cout<<endl;
  99.     input = "arex";
  100.     cout<<input << ":   ";
  101.     dict.checkroot(input); 
  102.     cout<<endl;
  103.     input = "basemexz";
  104.     cout<<input << ":   ";
  105.     dict.checkroot(input); 
  106.     cout<<endl;
  107.     input = "xyz";
  108.     cout<<input << ":   ";
  109.     dict.checkroot(input); 
  110.     cout<<endl;
  111.     return 0;
  112. }

$ g++ longest_prefix.cpp
$ a.out
 
caterer:   cater
basement:   basement
are:   are
arex:   are
basemexz:   baseme
xyz:
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.