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
}