Description:

A suffix array is a sorted array of all sub-strings of a given string. It can be constructed by performing a depth-first traversal of a suffix tree. It corresponds to the leaf-labels given in the order in which these are visited during the traversal, if edges are visited in the lexicographical order of their first character. A suffix tree can be constructed in linear time by using a combination of suffix array and longest common prefix array. The overall run-time for this algorithm is O(n^2 log n).

Program:

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <string>

using namespace std;

class Array

{

    private:

        string *txt;  

        string *suffix;   

        int *ind;

        int len;

    public:

        Array(string txt)

        {

            this->txt = new string[txt.length()]; 

            for (int i = 0; i < txt.length(); i++)

            {

                this->txt[i] = txt.substr(i, 1);

            } 

            this->len = txt.length();

            this->ind = new int[len];

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

            {

                ind[i] = i;

            }

            suffix = new string[len];

        }

        void createArray()

        {   

            for(int ind = 0; ind < len; ind++)

            {

                string txt = "";

                for (int txt_ind = ind; txt_ind < len; txt_ind++)

                {

                    txt += this->txt[txt_ind];

                } 

                suffix[ind] = txt;

            }

            int reverse;

            for (int iteration = 1; iteration < len; iteration++)

            {

                string key = suffix[iteration];

                int keyind = ind[iteration];

                for (reverse = iteration - 1; reverse >= 0; reverse--)

                {

                    if (suffix[reverse].compare(key) > 0)

                    {

                        suffix[reverse + 1] = suffix[reverse];

                        ind[reverse + 1] = ind[reverse];

                    }

                    else

                    {

                        break;

                    }

                }

                suffix[reverse + 1] = key;

                ind[reverse + 1 ] = keyind;

            }

            cout<<"SUFFIX \tINDEX VALUE"<<endl;

            for (int iterate = 0; iterate < len; iterate++)

            {

                cout<<suffix[iterate] << "\t" << ind[iterate]<<endl;

            }

        }

};

int main()

{

    string txt;

    cout<<"Enter the String: ";

    cin>>txt;

    Array array(txt);

    array.createArray();

}

Output:

Enter the String: Madam

SUFFIX          INDEX VALUE

Madam            0

adam               1

am                   3

dam                 2

m                     4