[AlgoMastery]
Topics›String›Suffix Arrays
📖

Suffix Arrays

String
~20 min read
5 practice problems

Overview

Suffix Array is a sorted array of all suffixes of a string. It's a space-efficient alternative to suffix trees, enabling fast substring search, longest common prefix (LCP), and pattern matching operations.

Key advantages:

  • Space-efficient: O(n) space vs O(n) for suffix tree
  • Fast substring search: O(m + log n) with binary search
  • Supports longest common prefix queries
  • Foundation for advanced string algorithms

Common suffix array problems include:

  • Substring search
  • Longest common substring
  • Longest repeated substring
  • Pattern matching
  • Suffix sorting
  • LCP array construction

Pattern 1: Basic Suffix Array Construction

Build a suffix array by sorting all suffixes.

function buildSuffixArray(s: string): number[] {
  const n = s.length;
  const suffixes: Array<{index: number, suffix: string}> = [];
  
  for (let i = 0; i < n; i++) {
    suffixes.push({
      index: i,
      suffix: s.substring(i)
    });
  }
  
  suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
  
  return suffixes.map(s => s.index);
}

Time: O(n^2 log n), Space: O(n^2)

Optimized construction (Manber-Myers algorithm):

function buildSuffixArrayOptimized(s: string): number[] {
  const n = s.length;
  const suffixArray: number[] = Array.from({length: n}, (_, i) => i);
  const rank: number[] = new Array(n);
  
  // Initial rank (single character)
  for (let i = 0; i < n; i++) {
    rank[i] = s.charCodeAt(i);
  }
  
  // Sort by first character
  suffixArray.sort((i, j) => rank[i] - rank[j]);
  
  // Double the prefix length in each iteration
  for (let k = 1; k < n; k *= 2) {
    const newRank: number[] = new Array(n);
    let r = 0;
    
    newRank[suffixArray[0]] = 0;
    
    for (let i = 1; i < n; i++) {
      const prev = suffixArray[i - 1];
      const curr = suffixArray[i];
      
      const prevRank = rank[prev];
      const currRank = rank[curr];
      const prevNextRank = (prev + k < n) ? rank[prev + k] : -1;
      const currNextRank = (curr + k < n) ? rank[curr + k] : -1;
      
      if (prevRank !== currRank || prevNextRank !== currNextRank) {
        r++;
      }
      
      newRank[curr] = r;
    }
    
    rank = newRank;
    
    // Sort by new rank
    suffixArray.sort((i, j) => {
      if (rank[i] !== rank[j]) return rank[i] - rank[j];
      const iNext = (i + k < n) ? rank[i + k] : -1;
      const jNext = (j + k < n) ? rank[j + k] : -1;
      return iNext - jNext;
    });
  }
  
  return suffixArray;
}

Time: O(n log^2 n), Space: O(n)

Pattern 2: Longest Common Prefix (LCP) Array

Build LCP array from suffix array.

function buildLCPArray(s: string, suffixArray: number[]): number[] {
  const n = s.length;
  const lcp: number[] = new Array(n);
  const rank: number[] = new Array(n);
  
  // Build rank array
  for (let i = 0; i < n; i++) {
    rank[suffixArray[i]] = i;
  }
  
  let k = 0;
  
  for (let i = 0; i < n; i++) {
    if (rank[i] === n - 1) {
      k = 0;
      continue;
    }
    
    const j = suffixArray[rank[i] + 1];
    
    while (i + k < n && j + k < n && s[i + k] === s[j + k]) {
      k++;
    }
    
    lcp[rank[i]] = k;
    
    if (k > 0) k--;
  }
  
  return lcp;
}

Time: O(n), Space: O(n)

Pattern 3: Substring Search

Search for pattern in string using suffix array.

function searchPattern(s: string, pattern: string, suffixArray: number[]): number[] {
  const n = s.length;
  const m = pattern.length;
  const results: number[] = [];
  
  // Binary search for lower bound
  let left = 0, right = n - 1;
  let lowerBound = n;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const suffix = s.substring(suffixArray[mid]);
    
    if (suffix >= pattern) {
      lowerBound = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  
  // Binary search for upper bound
  left = 0;
  right = n - 1;
  let upperBound = -1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const suffix = s.substring(suffixArray[mid]);
    
    if (suffix.startsWith(pattern)) {
      upperBound = mid;
      left = mid + 1;
    } else if (suffix < pattern) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  // Collect all occurrences
  for (let i = lowerBound; i <= upperBound; i++) {
    results.push(suffixArray[i]);
  }
  
  return results;
}

Time: O(m log n + occ) where occ is number of occurrences, Space: O(occ)

Pattern 4: Longest Repeated Substring

Find the longest substring that appears at least twice.

function longestRepeatedSubstring(s: string): string {
  const suffixArray = buildSuffixArray(s);
  const lcp = buildLCPArray(s, suffixArray);
  
  let maxLength = 0;
  let maxIndex = -1;
  
  for (let i = 0; i < lcp.length; i++) {
    if (lcp[i] > maxLength) {
      maxLength = lcp[i];
      maxIndex = suffixArray[i];
    }
  }
  
  if (maxLength === 0) return '';
  
  return s.substring(maxIndex, maxIndex + maxLength);
}

Time: O(n log^2 n), Space: O(n)

Pattern 5: Longest Common Substring

Find longest common substring between two strings.

function longestCommonSubstring(s1: string, s2: string): string {
  const separator = '#';
  const combined = s1 + separator + s2;
  const n = combined.length;
  
  const suffixArray = buildSuffixArray(combined);
  const lcp = buildLCPArray(combined, suffixArray);
  
  let maxLength = 0;
  let maxIndex = -1;
  
  for (let i = 1; i < n; i++) {
    const prevSuffix = suffixArray[i - 1];
    const currSuffix = suffixArray[i];
    
    // Check if suffixes come from different strings
    const prevInS1 = prevSuffix < s1.length;
    const currInS1 = currSuffix < s1.length;
    
    if (prevInS1 !== currInS1 && lcp[i - 1] > maxLength) {
      maxLength = lcp[i - 1];
      maxIndex = Math.min(prevSuffix, currSuffix);
    }
  }
  
  if (maxLength === 0) return '';
  
  return combined.substring(maxIndex, maxIndex + maxLength);
}

Time: O((n + m) log^2 (n + m)), Space: O(n + m)

Pattern 6: Distinct Substrings Count

Count number of distinct substrings.

function countDistinctSubstrings(s: string): number {
  const n = s.length;
  const suffixArray = buildSuffixArray(s);
  const lcp = buildLCPArray(s, suffixArray);
  
  // Total substrings = n * (n + 1) / 2
  // Subtract LCP values (overlapping prefixes)
  let total = (n * (n + 1)) / 2;
  
  for (let i = 0; i < lcp.length; i++) {
    total -= lcp[i];
  }
  
  return total;
}

Time: O(n log^2 n), Space: O(n)

Pattern 7: Longest Palindromic Substring

Find longest palindromic substring using suffix array.

function longestPalindromicSubstring(s: string): string {
  const reversed = s.split('').reverse().join('');
  const combined = s + '#' + reversed;
  const n = combined.length;
  
  const suffixArray = buildSuffixArray(combined);
  const lcp = buildLCPArray(combined, suffixArray);
  
  let maxLength = 0;
  let maxIndex = -1;
  
  for (let i = 1; i < n; i++) {
    const prevSuffix = suffixArray[i - 1];
    const currSuffix = suffixArray[i];
    
    // Check if one is in original, other in reversed
    const prevInOriginal = prevSuffix < s.length;
    const currInOriginal = currSuffix < s.length;
    
    if (prevInOriginal !== currInOriginal) {
      const lcpValue = lcp[i - 1];
      
      // Check if positions align for palindrome
      const pos1 = prevInOriginal ? prevSuffix : (n - 1 - currSuffix);
      const pos2 = currInOriginal ? currSuffix : (n - 1 - prevSuffix);
      
      if (lcpValue > maxLength && pos1 + lcpValue - 1 === pos2) {
        maxLength = lcpValue;
        maxIndex = Math.min(prevSuffix, currSuffix);
      }
    }
  }
  
  if (maxLength === 0) return s[0] || '';
  
  return combined.substring(maxIndex, maxIndex + maxLength);
}

Time: O(n log^2 n), Space: O(n)

Pattern 8: Suffix Array for Multiple Strings

Build suffix array for multiple strings.

function buildMultiStringSuffixArray(strings: string[]): Array<{index: number, stringIndex: number}> {
  const separator = '#';
  const combined: string[] = [];
  const stringIndices: number[] = [];
  
  let offset = 0;
  for (let i = 0; i < strings.length; i++) {
    for (let j = 0; j < strings[i].length; j++) {
      combined.push(strings[i][j]);
      stringIndices.push(i);
    }
    combined.push(separator);
    stringIndices.push(-1); // Separator
    offset += strings[i].length + 1;
  }
  
  const s = combined.join('');
  const suffixArray = buildSuffixArray(s);
  
  return suffixArray.map(index => ({
    index,
    stringIndex: stringIndices[index]
  })).filter(item => item.stringIndex !== -1);
}

Time: O(N log^2 N) where N is total length, Space: O(N)

Pattern 9: Pattern Matching with Wildcards

Search pattern with wildcards using suffix array.

function searchPatternWithWildcards(s: string, pattern: string): number[] {
  const results: number[] = [];
  const parts = pattern.split('*').filter(p => p.length > 0);
  
  if (parts.length === 0) {
    // Pattern is all wildcards
    for (let i = 0; i <= s.length; i++) {
      results.push(i);
    }
    return results;
  }
  
  const suffixArray = buildSuffixArray(s);
  
  // Find matches for first part
  const firstMatches = searchPattern(s, parts[0], suffixArray);
  
  for (const start of firstMatches) {
    let pos = start + parts[0].length;
    let valid = true;
    
    // Check remaining parts
    for (let i = 1; i < parts.length; i++) {
      const nextPos = s.indexOf(parts[i], pos);
      if (nextPos === -1) {
        valid = false;
        break;
      }
      pos = nextPos + parts[i].length;
    }
    
    if (valid) {
      results.push(start);
    }
  }
  
  return results;
}

Time: O(n log^2 n + m * occ), Space: O(n + occ)

Pattern 10: Suffix Array Range Queries

Answer range queries about suffixes efficiently.

class SuffixArrayRangeQuery {
  suffixArray: number[];
  lcp: number[];
  s: string;
  
  constructor(s: string) {
    this.s = s;
    this.suffixArray = buildSuffixArray(s);
    this.lcp = buildLCPArray(s, this.suffixArray);
  }
  
  // Find longest common prefix between two suffixes
  lcpQuery(i: number, j: number): number {
    const rankI = this.suffixArray.indexOf(i);
    const rankJ = this.suffixArray.indexOf(j);
    
    if (rankI === rankJ) return this.s.length - i;
    
    const minRank = Math.min(rankI, rankJ);
    const maxRank = Math.max(rankI, rankJ);
    
    let minLCP = Infinity;
    for (let k = minRank; k < maxRank; k++) {
      minLCP = Math.min(minLCP, this.lcp[k]);
    }
    
    return minLCP;
  }
  
  // Count distinct substrings in range
  countDistinctInRange(start: number, end: number): number {
    const n = end - start + 1;
    let total = (n * (n + 1)) / 2;
    
    // Calculate LCP for suffixes in range
    const rangeLCP: number[] = [];
    const rangeSuffixes = this.suffixArray.slice(start, end + 1);
    
    for (let i = 1; i < rangeSuffixes.length; i++) {
      const lcpValue = this.lcpQuery(rangeSuffixes[i - 1], rangeSuffixes[i]);
      rangeLCP.push(lcpValue);
      total -= lcpValue;
    }
    
    return total;
  }
}

Time: O(n log^2 n) construction, O(n) per query, Space: O(n)

Pattern 11: Suffix Array for Circular Strings

Handle circular string problems.

function buildCircularSuffixArray(s: string): number[] {
  const n = s.length;
  const doubled = s + s;
  const suffixes: Array<{index: number, suffix: string}> = [];
  
  for (let i = 0; i < n; i++) {
    suffixes.push({
      index: i,
      suffix: doubled.substring(i, i + n)
    });
  }
  
  suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
  
  return suffixes.map(s => s.index);
}

function lexicographicallySmallestRotation(s: string): string {
  const suffixArray = buildCircularSuffixArray(s);
  const startIndex = suffixArray[0];
  
  return s.substring(startIndex) + s.substring(0, startIndex);
}

Time: O(n^2 log n), Space: O(n^2)

Pattern 12: Suffix Array Compression

Compress suffix array for space efficiency.

class CompressedSuffixArray {
  suffixArray: number[];
  inverseSuffixArray: number[];
  
  constructor(s: string) {
    this.suffixArray = buildSuffixArray(s);
    this.inverseSuffixArray = new Array(s.length);
    
    for (let i = 0; i < this.suffixArray.length; i++) {
      this.inverseSuffixArray[this.suffixArray[i]] = i;
    }
  }
  
  // Get suffix at position i in sorted order
  getSuffix(rank: number): number {
    return this.suffixArray[rank];
  }
  
  // Get rank of suffix starting at index i
  getRank(index: number): number {
    return this.inverseSuffixArray[index];
  }
  
  // Compare two suffixes
  compareSuffixes(i: number, j: number): number {
    return this.getRank(i) - this.getRank(j);
  }
}

Time: O(n log^2 n) construction, O(1) queries, Space: O(n)

When to Use Suffix Array

Use suffix array when:

  • Problem involves substring search or pattern matching
  • Need to find longest common substring
  • Longest repeated substring problems
  • Distinct substring counting
  • Multiple string operations
  • Range queries on suffixes
  • Need space-efficient alternative to suffix tree

Template (Basic Suffix Array)

class SuffixArrayTemplate {
  suffixArray: number[];
  lcp: number[];
  s: string;
  
  constructor(s: string) {
    this.s = s;
    this.suffixArray = this.buildSuffixArray();
    this.lcp = this.buildLCPArray();
  }
  
  buildSuffixArray(): number[] {
    const n = this.s.length;
    const suffixes: Array<{index: number, suffix: string}> = [];
    
    for (let i = 0; i < n; i++) {
      suffixes.push({index: i, suffix: this.s.substring(i)});
    }
    
    suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
    return suffixes.map(s => s.index);
  }
  
  buildLCPArray(): number[] {
    // Implementation as shown in Pattern 2
    return [];
  }
}

Template (Binary Search on Suffix Array)

function binarySearchSuffixArray(
  s: string, 
  suffixArray: number[], 
  pattern: string,
  findLower: boolean
): number {
  let left = 0, right = suffixArray.length - 1;
  let result = findLower ? suffixArray.length : -1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const suffix = s.substring(suffixArray[mid]);
    
    const comparison = suffix.localeCompare(pattern);
    
    if (findLower) {
      if (comparison >= 0) {
        result = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (comparison <= 0) {
        result = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return result;
}

Time and Space Complexity Summary

  • Construction: O(n log^2 n) time, O(n) space
  • LCP array: O(n) time, O(n) space
  • Pattern search: O(m log n + occ) time, O(occ) space
  • Longest repeated substring: O(n log^2 n) time, O(n) space
  • Longest common substring: O((n + m) log^2 (n + m)) time, O(n + m) space
  • Distinct substrings: O(n log^2 n) time, O(n) space

Practice Tips

  1. Use optimized construction — Manber-Myers for better performance
  2. Understand LCP array — Key for many suffix array problems
  3. Binary search — Efficient pattern matching
  4. Handle separators — Use unique separators for multiple strings
  5. Space optimization — Consider compressed representations
  6. Preprocessing — Build suffix array once, query many times

Common Mistakes

  1. Off-by-one errors — Careful with array indices
  2. Separator handling — Use unique separators for multi-string
  3. LCP calculation — Ensure correct implementation
  4. Edge cases — Empty strings, single character
  5. Comparison order — Consistent lexicographic ordering

Related Concepts

  • Suffix Tree — Alternative data structure
  • String Matching — KMP, Rabin-Karp algorithms
  • Trie — For prefix matching
  • Binary Search — For pattern search

Suffix arrays are powerful for string problems. Master these patterns, and you'll be well-prepared for advanced string algorithm interview questions.

← PreviousTrie for StringsNext →Advanced String Matching