C++ Program to Implement Suffix Array

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

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

```
/*
```

 * C++ Program to Implement Suffix Array

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
#include <cstring>
```
```
#include <string>
```
```
using namespace std;
```
```
 
```
```
class SuffixArray
```
```
{
```
```
    private:
```
```
        string *text;
```
```
        int length;
```
```
        int *index;
```
```
        string *suffix;
```
```
    public:
```
```
        SuffixArray(string text)
```
```
        {
```

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

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

```
            {
```

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

```
            } 
```

            this->length = text.length();

            this->index = new int[length];

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

```
            {
```
```
                index[i] = i;
```
```
            }	
```

            suffix = new string[length];

```
        }
```
```
 
```
```
        void createSuffixArray()
```
```
        {   
```

            for(int index = 0; index < length; index++)

```
            {
```
```
                string text = "";
```

                for (int text_index = index; text_index < length; text_index++)

```
                {
```

                    text += this->text[text_index];

```
                } 
```
```
                suffix[index] = text;
```
```
            }
```
```
            int back;
```

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

```
            {
```

                string key = suffix[iteration];

                int keyindex = index[iteration];

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

```
                {
```

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

```
                    {
```

                        suffix[back + 1] = suffix[back];

                        index[back + 1] = index[back];

```
                    }
```
```
                    else
```
```
                    {
```
```
                        break;
```
```
                    }
```
```
                }
```
```
                suffix[back + 1] = key;
```

                index[back + 1 ] = keyindex;

```
            }
```

            cout<<"SUFFIX \t INDEX"<<endl;

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

```
            {		
```

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

```
            }
```
```
        }
```
```
};
```
```
 
```
```
int main()
```
```
{
```
```
    string text;
```
```
    cout<<"Enter the Text String: ";
```
```
    cin>>text;
```
```
    SuffixArray suffixarray(text);
```
```
    suffixarray.createSuffixArray();
```
```
}
```

$ g++ suffix_array.cpp
$ a.out
 
Enter the Text String: sanfoundry
SUFFIX        INDEX
anfoundry       1
dry             7
foundry         3
ndry            6
nfoundry        2
oundry          4
ry              8
sanfoundry      0
undry           5
y               9
 
 
------------------
(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 Sparse Array

» Next - C++ Program to Implement Bit Array

Related Posts:

Recommended Articles: