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.

```
/* 
```

 * C++ Program to Implement 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;
```
```
}
```

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

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

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Count Inversions in an Array

» Next - Modular Exponentiation Algorithm in C++

Related Posts:

Recommended Articles: