C++ Program to Implement Suffix Tree

This C++ Program demonstrates the implementation of Suffix Tree.

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

```
/*
```

 * C++ Program to Implement Suffix Tree

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
#include <cstring>
```
```
#include <string>
```
```
 
```
```
using namespace std;
```
```
typedef unsigned char byte;
```
```
/* 
```
```
 * SuffixNode Declaration
```
```
 */
```
```
class SuffixNode 
```
```
{
```
```
    public:
```
```
        int depth, begin, end;
```
```
        SuffixNode **children;
```

        SuffixNode *parent, *suffixLink;

```
        /* 
```
```
         * Constructor 
```
```
         */
```

        SuffixNode(int begin, int end, int depth, SuffixNode *parent)

```
        {
```

            children = new SuffixNode* [38];

```
            this->begin = begin;
```
```
            this->end = end;
```
```
            this->parent = parent;
```
```
            this->depth = depth;
```
```
        }
```
```
 
```
```
        bool contains(int d)
```
```
        {
```

            return depth <= d && d < depth + (end - begin);

```
        }    
```
```
};
```
```
string alphabet; 
```
```
int alphabetSize;
```
```
int lcsLength;
```
```
int lcsBeginIndex;
```
```
 
```
```
/* 
```
```
 * Class SuffixTree Declaration
```
```
 */
```
```
class SuffixTree 
```
```
{
```
```
    public:
```
```
        /* 
```

         * Funtion to build suffix tree for given text

```
         */
```

        SuffixNode *buildSuffixTree(string s)

```
        {
```
```
            int n = s.length();
```
```
            int *a = new int[n];
```

            for (int i = 0; i < n; i++)

```
            {
```

                a[i] = alphabet.find(s.at(i));

```
            }
```

            SuffixNode *root = new SuffixNode(0, 0, 0, NULL);

```
            SuffixNode *cn = root;
```
```
            root->suffixLink = root;
```

            SuffixNode *needsSuffixLink = NULL;

```
            int lastRule = 0;
```
```
            int j = 0;
```

            for (int i = -1; i < n - 1; i++)

```
            {
```
```
                int cur = a[i + 1]; 
```

                for (; j <= i + 1; j++)

```
                {
```

                    int curDepth = i + 1 - j;

```
                    if (lastRule != 3) 
```
```
                    {
```

                        if (cn->suffixLink != NULL)

                            cn = cn->suffixLink;

```
                        else
```

                            cn = cn->parent->suffixLink;

                        int k = j + cn->depth;

                        while (curDepth > 0 && !cn->contains(curDepth - 1))

```
                        {
```

                            k += cn->end - cn->begin;

                            cn = cn->children[a[k]];

```
                        }
```
```
                    }
```

                    if (!cn->contains(curDepth))

```
                    { 
```

                        if (needsSuffixLink != NULL)

```
                        {
```

                            needsSuffixLink->suffixLink = cn;

                            needsSuffixLink = NULL;

```
                        }
```

                        if (cn->children[cur] == NULL)

```
                        {
```

                            cn->children[cur] = new SuffixNode(i + 1, n, curDepth, cn);

                            lastRule = 2;

```
                        }
```
```
                        else 
```
```
                        {    
```

                            cn = cn->children[cur];

                            lastRule = 3;

```
                            break;
```
```
                        }
```
```
                    }
```
```
                    else 
```
```
                    { 
```

                        int end = cn->begin + curDepth - cn->depth;

                        if (a[end] != cur)

```
                        { 
```

                            SuffixNode *newn = new SuffixNode(cn->begin, end, cn->depth, cn->parent);

                            newn->children[cur] = new SuffixNode(i + 1, n, curDepth, newn);

                            newn->children[a[end]] = cn;

                            cn->parent->children[a[cn->begin]] = newn;

                            if (needsSuffixLink != NULL)

                                needsSuffixLink->suffixLink = newn;

                            cn->begin = end;

                            cn->depth = curDepth;

                            cn->parent = newn;

                            cn = needsSuffixLink = newn;

                            lastRule = 2;

```
                        } 
```

                        else if (cn->end != n || (cn->begin - cn->depth) < j)

```
                        {
```

                            lastRule = 3;

```
                            break;
```
```
                        }
```
```
                        else
```

                            lastRule = 1;

```
                    }
```
```
                }
```
```
            }
```
```
            root->suffixLink = NULL;
```
```
            return root;
```
```
        }        
```
```
        /* 
```

         * Funtion to find longest common substring

```
         */
```

        int findLCS(SuffixNode *node, int i1, int i2)

```
        {
```

            if (node->begin <= i1 && i1 < node->end)

```
                return 1;
```

            if (node->begin <= i2 && i2 < node->end)

```
                return 2;
```
```
            int mask = 0;
```

            for (int f = 0; f < alphabetSize; f++)

```
            { 
```

                if (node->children[f] != NULL)

```
                {   
```

                    mask |= findLCS(node->children[f], i1, i2);

```
                }
```
```
            }
```
```
            if (mask == 3)
```
```
            {
```

                int curLength = node->depth + node->end - node->begin;

                if (lcsLength < curLength)

```
                {
```

                    lcsLength = curLength;

                    lcsBeginIndex = node->begin;

```
                }
```
```
            }
```
```
            return mask;
```
```
        }
```
```
 
```
```
        /* 
```

         * Funtion to find longest common substring

```
         */
```

        void findLCS(string s1, string s2)

```
        {
```
```
            string x = "-";
```
```
            string y = "#";
```
```
            string ns1 = s1;
```
```
            string ns2 = s2;
```

            string s = s1.append(x.append(s2.append(y)));

            SuffixNode *root = buildSuffixTree(s);

```
            lcsLength = 0;
```

            lcsBeginIndex = 0;

            findLCS(root, ns1.length(), ns1.length() + ns2.length() + 1);

```
            bool chk = lcsLength > 0;
```
```
            if (chk)
```
```
            {
```

                cout<<"\nLongest substring is "<<s.substr(lcsBeginIndex , lcsLength);

```
                cout<<endl; 
```
```
            }
```
```
            else
```
```
            {
```

                cout<<"No substring found"<<endl;

```
            }
```
```
        }
```
```
};
```
```
 
```
```
/* 
```
```
 * Main 
```
```
*/
```
```
int main()
```
```
{
```

    alphabet = "abcdefghijklmnopqrstuvwxyz1234567890-#";

```
    alphabetSize = alphabet.length();
```
```
    string s1,s2;
```

    cout<<"Finding longest common substring using suffix trees\n";

```
    cout<<"Enter 1st String: ";
```
```
    cin>>s1; 
```
```
    cout<<"Enter 2nd String: ";
```
```
    cin>>s2;
```
```
    SuffixTree st;
```
```
    st.findLCS(s1, s2);         
```
```
    return 0;
```
```
}
```

$ g++ suffixtree.cpp
$ a.out
 
Finding longest common substring using suffix trees
Enter 1st String: sanfoundry
Enter 2nd String: founder
 
Longest substring is found
 
 
------------------
(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.

« Prev - C++ Program to Implement Splay Tree

» Next - C++ Program to Implement Ternary Tree

Related Posts:

Apply for Computer Science Internship
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs
Practice Computer Science MCQs

Recommended Articles: