Suffix Array 🎯

Welcome to the exciting world of Data Structures and Algorithms! Today, we'll delve into the topic of Suffix Array. This powerful tool is a versatile data structure used in string processing, sorting, and algorithmic problems. Let's get started!

What is a Suffix Array? 📝

A Suffix Array is an array of all suffixes of a given string, sorted lexicographically. It provides us with a compact and efficient way to access all unique suffixes of a string and their lexicographical order.

Why use a Suffix Array? 💡

Suffix Arrays are useful in several real-world applications like text editing, pattern matching, longest common substring, and many more. They offer advantages over traditional sorting methods by providing a more space-efficient and faster solution for sorting large strings.

Building a Suffix Array 💡

The construction of a Suffix Array involves three main steps:

Creating all suffixes of the given string
Sorting the suffixes lexicographically
Constructing the Suffix Array from the sorted suffixes

Let's dive into each step!

Step 1: Creating all suffixes 📝

To create all suffixes, we simply concatenate the original string with a special symbol (like $) and then generate all substrings ending with that symbol. This way, we have all suffixes of the original string.

For example, given the string "banana", the suffix array would be:

banana$
anana$
nana$
ana$
na$
a$
$

Step 2: Sorting the suffixes 💡

Now that we have all suffixes, we need to sort them lexicographically. A common method for this is using a comparison-based sorting algorithm like MergeSort or QuickSort. However, since the suffixes are all of the same length, a faster method called Counting Sort can be used.

Step 3: Constructing the Suffix Array 💡

Finally, we construct the Suffix Array using the sorted suffixes. This is done by creating an array where the i-th element stores the position of the i-th sorted suffix in the original string.

For our example, the Suffix Array would be:

7 (banana$)
0 (banana)
6 (anana$)
1 (anana)
5 (nana$)
2 (nana)
3 (ana$)
4 (ana)

Applications of Suffix Arrays 💡

Suffix Arrays have numerous applications in computer science, some of which include:

Longest Common Substring
Longest Repeating Subsequence
Pattern Matching
KMP Algorithm Optimization
Ukkonen's Algorithm for Constructing Suffix Trees

Quiz Time! 🎯

Code Examples 💡

Here are two complete working examples in C++ and Python demonstrating the construction of a Suffix Array.

C++

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX_CHAR = 256;

void suffix_array(string &text, vector<int> &sa, vector<int> &rank, vector<int> &count) {
    int n = text.length();
    sa.resize(n);
    rank.resize(n);
    count.resize(MAX_CHAR);

    for (int i = 0; i < n; i++) {
        sa[i] = i;
        count[text[i]]++;
    }

    for (int k = 1; k < MAX_CHAR; k++) {
        for (int i = k; i < MAX_CHAR; i++) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            sa[count[text[i]] - 1] = i;
            count[text[i]]--;
        }

        int t = 0;
        for (int i = 0; i < MAX_CHAR; i++) {
            count[i] = t;
            t += count[i];
        }

        if (n == rank.size()) {
            break;
        }

        for (int i = n - 1; i >= 0; i--) {
            int j = sa[i] - 1;
            if (i + n < 2 * n && sa[i + n] == sa[j + n] && text[i] == text[j]) {
                rank[i] = rank[j];
            } else {
                rank[i] = (text[sa[i]] < text[sa[j]]) ? rank[j] + 1 : rank[j];
            }
        }

        t = 0;
        for (int i = 0; i < n; i++) {
            count[rank[i]]++;
            t += count[rank[i]];
            count[rank[i]] = t;
        }
    }
}

Python

python

import sys

def suffix_array(text):
    n = len(text)
    sa = list(range(n))
    rank = [0] * n

    for k in range(1, n + 1):
        count = [0] * 256

        for i in range(n):
            sa_i = sa[i] + k < n and text[sa[i] + k] == text[sa[i]]
            count[ord(text[i])] += sa_i

        total = sum(count)
        for i in range(n):
            sa[count[ord(text[i])]] = i
            count[ord(text[i])] += total - sa[count[ord(text[i])]]

    for k in range(1, n * 2):
        count = [0] * n

        for i in range(n):
            j = sa[i] - 1
            if k < n and sa[i] + k < n and text[i] == text[j] and sa[i + k] == sa[j + k]:
                rank[i] = rank[j]
            else:
                rank[i] = (text[sa[i]] < text[sa[j]]) and rank[j] + 1 or rank[j]

        temp = [0] * n
        for i in range(n):
            temp[rank[i]] = sa[i]
            count[rank[i]] += 1

        for i in range(1, n):
            count[i] += count[i - 1]

        for i in range(n - 1, -1, -1):
            sa[count[rank[i]]] = temp[i]
            count[rank[i]] -= 1

    return sa

Conclusion 💡

Suffix Arrays are a powerful tool in string processing and algorithmic problems. They offer a more space-efficient and faster solution for sorting large strings. By understanding and mastering Suffix Arrays, you'll unlock a plethora of opportunities to solve complex problems in the field of computer science.

Happy coding! 💻🙌