Suffix Array & Suffix Tree String Algorithms Tutorial

Introduction

Suffix arrays and suffix trees are powerful data structures used in advanced string matching algorithms. They allow you to efficiently search patterns, find repeated substrings, and solve complex problems like plagiarism detection, DNA sequencing, and text indexing.

In this suffix array tutorial, we will explore both suffix arrays and suffix trees, understand their differences, and learn how to implement them in code.

For Pakistani students preparing for competitive programming (e.g., FAST, NUST, or ICPC-style contests), mastering these concepts can give you a serious edge. Many advanced problems on platforms like Codeforces and LeetCode rely on these techniques.

Prerequisites

Before diving in, make sure you are comfortable with:

• Basic string operations (substring, prefix, suffix)
• Arrays and sorting algorithms
• Time complexity (Big-O notation)
• Recursion and trees (for suffix tree understanding)
• Basic C++ or Python programming

Core Concepts & Explanation

Suffixes of a String

A suffix of a string is any substring that starts at a position and goes to the end.

Example:
String = "karachi"

Suffixes:

karachi
arachi
rachi
achi
chi
hi
i

Suffix Array: Sorted Suffix Indexes

A suffix array is an array of indices that represent the starting positions of sorted suffixes.

Example:

String: banana

Suffixes:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

Sorted:
5: a
3: ana
1: anana
0: banana
4: na
2: nana

Suffix Array = [5, 3, 1, 0, 4, 2]

This allows binary search for pattern matching.

Longest Common Prefix (LCP) Array

The LCP array stores the length of the longest common prefix between consecutive suffixes.

Example:

LCP = [0, 1, 3, 0, 0, 2]

Why important?

• Helps in substring queries
• Used in longest repeated substring problems

Suffix Tree: Compressed Trie of Suffixes

A suffix tree is a compressed trie of all suffixes of a string.

Key properties:

• Built in O(n)
• Allows pattern search in O(m)
• Uses more memory than suffix array

Example idea:

• Each path represents a substring
• Leaves represent suffixes

Suffix Array vs Suffix Tree

Practical Code Examples

Example 1: Build Suffix Array (O(n log n))

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

vector<int> buildSuffixArray(string s) {
    int n = s.size();
    vector<int> sa(n), rank(n), temp(n);

    for (int i = 0; i < n; i++) {
        sa[i] = i;          // store suffix index
        rank[i] = s[i];     // initial rank by character
    }

    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j])
                return rank[i] < rank[j];
            int ri = i + k < n ? rank[i + k] : -1;
            int rj = j + k < n ? rank[j + k] : -1;
            return ri < rj;
        };

        sort(sa.begin(), sa.end(), cmp);

        temp[sa[0]] = 0;

        for (int i = 1; i < n; i++) {
            temp[sa[i]] = temp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
        }

        rank = temp;
    }

    return sa;
}

Line-by-line Explanation:

• sa[i] = i: stores starting index of suffix
• rank[i] = s[i]: initial ranking by ASCII value
• Loop k *= 2: compares substrings of length 2k
• cmp: custom comparator for sorting suffixes
• sort: sorts suffix indices
• temp: assigns new ranks after sorting
• Final sa: sorted suffix indices

Example 2: Pattern Search Using Suffix Array

Real-world scenario:
Ahmad is building a search engine for Urdu/English text in Islamabad.

bool searchPattern(string text, string pattern, vector<int>& sa) {
    int n = text.size();
    int m = pattern.size();

    int left = 0, right = n - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        string suffix = text.substr(sa[mid], m);

        if (suffix == pattern)
            return true;
        else if (suffix < pattern)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return false;
}

Line-by-line Explanation:

• sa[mid]: gives index of suffix
• substr: extracts prefix of suffix
• Binary search used → O(m log n)
• Efficient for large datasets (e.g., Pakistani news archives)

Common Mistakes & How to Avoid Them

Mistake 1: Incorrect Ranking Update

Students often forget to update ranks correctly.

❌ Wrong:

rank[i] = temp[i]

✔️ Correct:

rank = temp;

Reason: Entire array must be updated, not individual elements.

Mistake 2: Out-of-Bounds in Comparisons

When comparing i + k, index may exceed string length.

❌ Wrong:

rank[i + k]

✔️ Correct:

(i + k < n) ? rank[i + k] : -1

Practice Exercises

Exercise 1: Longest Repeated Substring

Problem:
Given a string, find the longest substring that appears more than once.

Solution Idea:

• Build suffix array
• Compute LCP array
• Maximum LCP value = answer

Exercise 2: Count Distinct Substrings

Problem:
Count total unique substrings.

Solution:

Total substrings = n(n+1)/2
Distinct = Total - sum(LCP)

Frequently Asked Questions

What is the difference between suffix array and suffix tree?

Suffix array stores sorted suffix indices, while suffix tree is a compressed trie. Arrays are memory efficient, trees are faster for queries.

How do I build suffix array efficiently?

Use the doubling algorithm (O(n log n)) or advanced algorithms like SA-IS for O(n).

Why is LCP important?

It helps avoid recomputation of prefixes and is used in problems like longest repeated substring.

Can I use suffix array in competitive programming?

Yes! It is widely used in Codeforces, ICPC, and FAST/NUST exams for string problems.

Which is better: suffix array or suffix tree?

For most practical uses, suffix array is preferred due to simplicity and lower memory usage.

Summary & Key Takeaways

• Suffix array sorts all suffixes of a string efficiently
• LCP array enhances performance in substring queries
• Suffix tree allows faster search but is complex
• Binary search + suffix array = efficient pattern matching
• Useful in real-world applications like search engines and DNA analysis

Next Steps & Related Tutorials

To deepen your understanding, explore:

• Learn prefix-based searching in our Trie Data Structure tutorial
• Optimize problems using Dynamic Programming techniques
• Understand fast range queries with Segment Trees tutorial
• Improve connectivity problems using Union-Find (Disjoint Set)

These topics are available on theiqra.edu.pk and will help you master advanced Data Structures & Algorithms 🚀