AntInLoop

Suffix Array & Kasai's LCP Algorithm Code Implementations

Complete Suffix Array & Kasai's LCP Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Suffix Array & Kasai's LCP Algorithm Guide · Launch Interactive Visualizer

C++ Implementation

// Suffix Array Implementation in C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <chrono>

class SuffixArray {
public:
    // Build suffix array using sorting
    static std::vector<int> buildSuffixArray(const std::string& str) {
        int n = str.length();
        std::vector<std::pair<int, std::string>> suffixes;
        
        // Generate all suffixes
        for (int i = 0; i < n; i++) {
            suffixes.emplace_back(i, str.substr(i));
        }
        
        // Sort suffixes lexicographically
        std::sort(suffixes.begin(), suffixes.end(), 
                 [](const auto& a, const auto& b) { return a.second < b.second; });
        
        // Extract indices
        std::vector<int> suffixArray(n);
        for (int i = 0; i < n; i++) {
            suffixArray[i] = suffixes[i].first;
        }
        
        return suffixArray;
    }
    
    // Build LCP (Longest Common Prefix) array
    static std::vector<int> buildLCPArray(const std::string& str, const std::vector<int>& suffixArray) {
        int n = str.length();
        std::vector<int> lcp(n - 1, 0);
        std::vector<int> rank(n, 0);
        
        // Build rank array
        for (int i = 0; i < n; i++) {
            rank[suffixArray[i]] = i;
        }
        
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (rank[i] == n - 1) {
                k = 0;
                continue;
            }
            
            int j = suffixArray[rank[i] + 1];
            while (i + k < n && j + k < n && str[i + k] == str[j + k]) {
                k++;
            }
            
            lcp[rank[i]] = k;
            if (k > 0) k--;
        }
        
        return lcp;
    }
    
    // Search pattern in suffix array
    static std::vector<int> searchPattern(const std::string& str, const std::vector<int>& suffixArray, 
                                        const std::string& pattern) {
        int n = str.length();
        int m = pattern.length();
        
        // Binary search for pattern
        int left = 0, right = n - 1;
        int start = -1, end = -1;
        
        // Find leftmost occurrence
        while (left <= right) {
            int mid = (left + right) / 2;
            std::string suffix = str.substr(suffixArray[mid]);
            int cmp = suffix.compare(0, m, pattern);
            
            if (cmp >= 0) {
                if (suffix.substr(0, m) == pattern) {
                    start = mid;
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // Find rightmost occurrence
        left = 0;
        right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            std::string suffix = str.substr(suffixArray[mid]);
            
            if (suffix.substr(0, m) == pattern) {
                end = mid;
                left = mid + 1;
            } else if (suffix > pattern) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        if (start == -1) return {};
        
        std::vector<int> matches;
        for (int i = start; i <= end; i++) {
            matches.push_back(suffixArray[i]);
        }
        
        std::sort(matches.begin(), matches.end());
        return matches;
    }
    
    // Find longest repeated substring
    static std::string findLongestRepeatedSubstring(const std::string& str, const std::vector<int>& suffixArray, 
                                                   const std::vector<int>& lcpArray) {
        int maxLength = 0;
        int maxIndex = 0;
        
        for (int i = 0; i < lcpArray.size(); i++) {
            if (lcpArray[i] > maxLength) {
                maxLength = lcpArray[i];
                maxIndex = suffixArray[i];
            }
        }
        
        return maxLength > 0 ? str.substr(maxIndex, maxLength) : "";
    }
    
    // Find all repeated substrings
    static std::vector<std::string> findAllRepeatedSubstrings(const std::string& str, 
                                                             const std::vector<int>& suffixArray, 
                                                             const std::vector<int>& lcpArray, 
                                                             int minLength = 2) {
        std::vector<std::string> repeated;
        
        for (int i = 0; i < lcpArray.size(); i++) {
            if (lcpArray[i] >= minLength) {
                std::string substring = str.substr(suffixArray[i], lcpArray[i]);
                repeated.push_back(substring);
            }
        }
        
        return repeated;
    }
    
    // Suffix array with performance measurement
    struct SuffixArrayResult {
        std::vector<int> suffixArray;
        std::vector<int> lcpArray;
        long long executionTime;
        
        SuffixArrayResult(const std::vector<int>& sa, const std::vector<int>& lcp, long long time) 
            : suffixArray(sa), lcpArray(lcp), executionTime(time) {}
    };
    
    static SuffixArrayResult suffixArrayWithTiming(const std::string& str) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> suffixArray = buildSuffixArray(str);
        std::vector<int> lcpArray = buildLCPArray(str, suffixArray);
        auto end = std::chrono::high_resolution_clock::now();
        
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        return SuffixArrayResult(suffixArray, lcpArray, duration.count());
    }
    
    // Performance comparison
    static void comparePerformance(const std::string& str) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> suffixArray = buildSuffixArray(str);
        std::vector<int> lcpArray = buildLCPArray(str, suffixArray);
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        
        std::cout << "Suffix Array built in " << duration.count() << " μs" << std::endl;
        std::cout << "String length: " << str.length() << std::endl;
        std::cout << "Suffix array size: " << suffixArray.size() << std::endl;
    }
};

JAVA Implementation

// Suffix Array Implementation in Java

import java.util.*;

public class SuffixArray {
    // Build suffix array using sorting
    public static int[] buildSuffixArray(String str) {
        int n = str.length();
        Suffix[] suffixes = new Suffix[n];
        
        // Generate all suffixes
        for (int i = 0; i < n; i++) {
            suffixes[i] = new Suffix(i, str.substring(i));
        }
        
        // Sort suffixes lexicographically
        Arrays.sort(suffixes);
        
        // Extract indices
        int[] suffixArray = new int[n];
        for (int i = 0; i < n; i++) {
            suffixArray[i] = suffixes[i].index;
        }
        
        return suffixArray;
    }
    
    static class Suffix implements Comparable<Suffix> {
        int index;
        String suffix;
        
        Suffix(int index, String suffix) {
            this.index = index;
            this.suffix = suffix;
        }
        
        @Override
        public int compareTo(Suffix other) {
            return this.suffix.compareTo(other.suffix);
        }
    }
    
    // Build LCP (Longest Common Prefix) array
    public static int[] buildLCPArray(String str, int[] suffixArray) {
        int n = str.length();
        int[] lcp = new int[n - 1];
        int[] rank = new int[n];
        
        // Build rank array
        for (int i = 0; i < n; i++) {
            rank[suffixArray[i]] = i;
        }
        
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (rank[i] == n - 1) {
                k = 0;
                continue;
            }
            
            int j = suffixArray[rank[i] + 1];
            while (i + k < n && j + k < n && str.charAt(i + k) == str.charAt(j + k)) {
                k++;
            }
            
            lcp[rank[i]] = k;
            if (k > 0) k--;
        }
        
        return lcp;
    }
    
    // Search pattern in suffix array
    public static List<Integer> searchPattern(String str, int[] suffixArray, String pattern) {
        int n = str.length();
        int m = pattern.length();
        
        // Binary search for pattern
        int left = 0, right = n - 1;
        int start = -1, end = -1;
        
        // Find leftmost occurrence
        while (left <= right) {
            int mid = (left + right) / 2;
            String suffix = str.substring(suffixArray[mid]);
            int cmp = suffix.compareTo(pattern);
            
            if (cmp >= 0) {
                if (suffix.startsWith(pattern)) {
                    start = mid;
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // Find rightmost occurrence
        left = 0;
        right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            String suffix = str.substring(suffixArray[mid]);
            
            if (suffix.startsWith(pattern)) {
                end = mid;
                left = mid + 1;
            } else if (suffix.compareTo(pattern) > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        if (start == -1) return new ArrayList<>();
        
        List<Integer> matches = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            matches.add(suffixArray[i]);
        }
        
        Collections.sort(matches);
        return matches;
    }
    
    // Find longest repeated substring
    public static String findLongestRepeatedSubstring(String str, int[] suffixArray, int[] lcpArray) {
        int maxLength = 0;
        int maxIndex = 0;
        
        for (int i = 0; i < lcpArray.length; i++) {
            if (lcpArray[i] > maxLength) {
                maxLength = lcpArray[i];
                maxIndex = suffixArray[i];
            }
        }
        
        return maxLength > 0 ? str.substring(maxIndex, maxIndex + maxLength) : "";
    }
    
    // Find all repeated substrings
    public static Set<String> findAllRepeatedSubstrings(String str, int[] suffixArray, int[] lcpArray, int minLength) {
        Set<String> repeated = new HashSet<>();
        
        for (int i = 0; i < lcpArray.length; i++) {
            if (lcpArray[i] >= minLength) {
                String substring = str.substring(suffixArray[i], suffixArray[i] + lcpArray[i]);
                repeated.add(substring);
            }
        }
        
        return repeated;
    }
    
    // Suffix array with performance measurement
    public static class SuffixArrayResult {
        public int[] suffixArray;
        public int[] lcpArray;
        public long executionTime;
        
        public SuffixArrayResult(int[] sa, int[] lcp, long time) {
            this.suffixArray = sa;
            this.lcpArray = lcp;
            this.executionTime = time;
        }
    }
    
    public static SuffixArrayResult suffixArrayWithTiming(String str) {
        long startTime = System.nanoTime();
        int[] suffixArray = buildSuffixArray(str);
        int[] lcpArray = buildLCPArray(str, suffixArray);
        long endTime = System.nanoTime();
        
        return new SuffixArrayResult(suffixArray, lcpArray, endTime - startTime);
    }
}

JAVASCRIPT Implementation

// Suffix Array Implementation in JavaScript

// Build suffix array using sorting
function buildSuffixArray(str) {
  const n = str.length;
  const suffixes = [];
  
  // Generate all suffixes
  for (let i = 0; i < n; i++) {
    suffixes.push({
      index: i,
      suffix: str.substring(i)
    });
  }
  
  // Sort suffixes lexicographically
  suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
  
  // Extract indices
  return suffixes.map(s => s.index);
}

// Build suffix array using DC3/Skew algorithm
function buildSuffixArrayDC3(str) {
  const n = str.length;
  if (n <= 1) return [0];
  
  // Add sentinel character
  const s = str + '
      

Loading AntInLoop...

#39;; const n2 = s.length; // Step 1: Sort suffixes starting at positions i mod 3 != 0 const sa12 = []; for (let i = 0; i < n2; i++) { if (i % 3 !== 0) { sa12.push(i); } } // Sort sa12 based on first 3 characters sa12.sort((a, b) => { for (let i = 0; i < 3; i++) { const charA = a + i < n2 ? s.charCodeAt(a + i) : 0; const charB = b + i < n2 ? s.charCodeAt(b + i) : 0; if (charA !== charB) return charA - charB; } return 0; }); // Step 2: Build suffix array for positions i mod 3 == 0 const sa0 = []; for (let i = 0; i < n2; i++) { if (i % 3 === 0) { sa0.push(i); } } // Merge sa0 and sa12 const sa = []; let i = 0, j = 0; while (i < sa0.length && j < sa12.length) { const pos0 = sa0[i]; const pos12 = sa12[j]; if (compareSuffixes(s, pos0, pos12) <= 0) { sa.push(pos0); i++; } else { sa.push(pos12); j++; } } // Add remaining elements while (i < sa0.length) sa.push(sa0[i++]); while (j < sa12.length) sa.push(sa12[j++]); return sa.filter(pos => pos < n); } function compareSuffixes(s, i, j) { const n = s.length; while (i < n && j < n) { if (s.charCodeAt(i) !== s.charCodeAt(j)) { return s.charCodeAt(i) - s.charCodeAt(j); } i++; j++; } return (n - i) - (n - j); } // Build LCP (Longest Common Prefix) array function buildLCPArray(str, suffixArray) { const n = str.length; const lcp = new Array(n - 1).fill(0); const rank = new Array(n).fill(0); // 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 && str[i + k] === str[j + k]) { k++; } lcp[rank[i]] = k; if (k > 0) k--; } return lcp; } // Search pattern in suffix array function searchPattern(str, suffixArray, pattern) { const n = str.length; const m = pattern.length; // Binary search for pattern let left = 0, right = n - 1; let start = -1, end = -1; // Find leftmost occurrence while (left <= right) { const mid = Math.floor((left + right) / 2); const suffix = str.substring(suffixArray[mid]); const cmp = suffix.localeCompare(pattern); if (cmp >= 0) { if (suffix.startsWith(pattern)) { start = mid; } right = mid - 1; } else { left = mid + 1; } } // Find rightmost occurrence left = 0; right = n - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); const suffix = str.substring(suffixArray[mid]); if (suffix.startsWith(pattern)) { end = mid; left = mid + 1; } else if (suffix.localeCompare(pattern) > 0) { right = mid - 1; } else { left = mid + 1; } } if (start === -1) return []; const matches = []; for (let i = start; i <= end; i++) { matches.push(suffixArray[i]); } return matches.sort((a, b) => a - b); } // Find longest repeated substring function findLongestRepeatedSubstring(str, suffixArray, lcpArray) { let maxLength = 0; let maxIndex = 0; for (let i = 0; i < lcpArray.length; i++) { if (lcpArray[i] > maxLength) { maxLength = lcpArray[i]; maxIndex = suffixArray[i]; } } return maxLength > 0 ? str.substring(maxIndex, maxIndex + maxLength) : ""; } // Find all repeated substrings function findAllRepeatedSubstrings(str, suffixArray, lcpArray, minLength = 2) { const repeated = new Set(); for (let i = 0; i < lcpArray.length; i++) { if (lcpArray[i] >= minLength) { const substring = str.substring(suffixArray[i], suffixArray[i] + lcpArray[i]); repeated.add(substring); } } return Array.from(repeated); } // Suffix array with performance measurement function suffixArrayWithTiming(str) { const startTime = performance.now(); const suffixArray = buildSuffixArray(str); const lcpArray = buildLCPArray(str, suffixArray); const endTime = performance.now(); return { suffixArray, lcpArray, executionTime: endTime - startTime }; }

PYTHON Implementation

# Suffix Array Implementation in Python

def build_suffix_array(s):
    """Build suffix array using sorting"""
    n = len(s)
    suffixes = [(i, s[i:]) for i in range(n)]
    suffixes.sort(key=lambda x: x[1])
    return [suffix[0] for suffix in suffixes]

def build_suffix_array_dc3(s):
    """Build suffix array using DC3/Skew algorithm"""
    n = len(s)
    if n <= 1:
        return [0]
    
    # Add sentinel character
    s = s + '
      

Loading AntInLoop...

#39; n2 = len(s) # Step 1: Sort suffixes starting at positions i mod 3 != 0 sa12 = [i for i in range(n2) if i % 3 != 0] # Sort sa12 based on first 3 characters def compare_triple(a, b): for i in range(3): char_a = ord(s[a + i]) if a + i < n2 else 0 char_b = ord(s[b + i]) if b + i < n2 else 0 if char_a != char_b: return char_a - char_b return 0 sa12.sort(key=lambda x: (s[x], s[x + 1] if x + 1 < n2 else '

Loading AntInLoop...

#39;, s[x + 2] if x + 2 < n2 else '

Loading AntInLoop...

#39;)) # Step 2: Build suffix array for positions i mod 3 == 0 sa0 = [i for i in range(n2) if i % 3 == 0] # Merge sa0 and sa12 sa = [] i = j = 0 while i < len(sa0) and j < len(sa12): pos0, pos12 = sa0[i], sa12[j] if compare_suffixes(s, pos0, pos12) <= 0: sa.append(pos0) i += 1 else: sa.append(pos12) j += 1 # Add remaining elements sa.extend(sa0[i:]) sa.extend(sa12[j:]) return [pos for pos in sa if pos < n] def compare_suffixes(s, i, j): """Compare two suffixes""" n = len(s) while i < n and j < n: if s[i] != s[j]: return ord(s[i]) - ord(s[j]) i += 1 j += 1 return (n - i) - (n - j) def build_lcp_array(s, suffix_array): """Build LCP (Longest Common Prefix) array""" n = len(s) lcp = [0] * (n - 1) rank = [0] * n # Build rank array for i in range(n): rank[suffix_array[i]] = i k = 0 for i in range(n): if rank[i] == n - 1: k = 0 continue j = suffix_array[rank[i] + 1] while i + k < n and j + k < n and s[i + k] == s[j + k]: k += 1 lcp[rank[i]] = k if k > 0: k -= 1 return lcp def search_pattern(s, suffix_array, pattern): """Search pattern in suffix array""" n = len(s) m = len(pattern) # Binary search for pattern left, right = 0, n - 1 start = end = -1 # Find leftmost occurrence while left <= right: mid = (left + right) // 2 suffix = s[suffix_array[mid]:] cmp_result = suffix[:m] == pattern if cmp_result or suffix > pattern: if suffix.startswith(pattern): start = mid right = mid - 1 else: left = mid + 1 # Find rightmost occurrence left, right = 0, n - 1 while left <= right: mid = (left + right) // 2 suffix = s[suffix_array[mid]:] if suffix.startswith(pattern): end = mid left = mid + 1 elif suffix > pattern: right = mid - 1 else: left = mid + 1 if start == -1: return [] matches = [suffix_array[i] for i in range(start, end + 1)] return sorted(matches) def find_longest_repeated_substring(s, suffix_array, lcp_array): """Find longest repeated substring""" max_length = 0 max_index = 0 for i in range(len(lcp_array)): if lcp_array[i] > max_length: max_length = lcp_array[i] max_index = suffix_array[i] return s[max_index:max_index + max_length] if max_length > 0 else "" def find_all_repeated_substrings(s, suffix_array, lcp_array, min_length=2): """Find all repeated substrings""" repeated = set() for i in range(len(lcp_array)): if lcp_array[i] >= min_length: substring = s[suffix_array[i]:suffix_array[i] + lcp_array[i]] repeated.add(substring) return list(repeated) def suffix_array_with_timing(s): """Suffix array with performance measurement""" import time start_time = time.time() suffix_array = build_suffix_array(s) lcp_array = build_lcp_array(s, suffix_array) end_time = time.time() return { 'suffix_array': suffix_array, 'lcp_array': lcp_array, 'execution_time': end_time - start_time }