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. }

advertisement
$ 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.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn