This is an implementation of Simple Linear Work Suffix Array Construction (2003) by Juha Karkkainen, Peter Sanders, and Stefan Burkhardt.
Implementation Copyright 2010 Google Inc. Distributed under the Apache 2.0 License.
For more details see LICENSE and public/dc3.h
Say you have a long string of text (think book-length) and you would like to find the longest string in the text that is repeated. One way to do this is to create a data structure called a suffix array. As an example, let's take the string "bananarama."
Suffixes of "bananarama":
bananarama
ananarama
nanarama
anarama
narama
arama
rama
ama
ma
a
A Suffix Array is simply the lexicographic ordering of these suffixes:
LCP SA Suffixes (ordered lexicographically)
1 9 a
1 7 ama
3 1 ananarama
1 3 anarama
0 5 arama
0 0 bananarama
0 8 ma
2 2 nanarama
0 6 narama
0 4 rama
There's no need to actually allocate new space for the suffixes -- you can just present the order of their indices in the original string.
The longest repeated substring of "bananarama" is "ana" and can be seen by looking down the suffix array and noting which pair of (subsequent) suffixes overlap the most. The Longest Common Prefix array (LCP) is what makes that part easy. LCP[i] holds the length of the overlap of the suffixes starting from SA[i] and SA[i+1].
Since we use a Sparse Tree Range Minimum Query, our costs are
O(n log n) instead of O(n). This could be improved.
- Memory (in integers):
~ N * (13 + 2/9 log (2N/3)) - Worst Case Time:
O(N log N)
#include "third_party/dc3/public/dc3.h"
int *LCP, *SA;
string interesting_text;
// Memory limit should reflect the max allowed memory usage.
DC3::SuffixArray(interesting_text, &SA, &LCP,
(interesting_text.size() + 4) * (20 * sizeof(int)));
int max_lcp_idx = 0;
for (int i = 1; i < interesting_text.size(); i++) {
if (LCP[i] > LCP[max_lcp_idx])
max_lcp_idx = i;
}
cout << "The longest repeated string is: \""
<< interesting_text.substr(max_lcp_idx, LCP[max_lcp_idx])
<< "\" which occurs at positions " << SA[max_lcp_idx]
<< " and " << SA[max_lcp_idx + 1];To build and install the library in an Open Source environment:
# Clone the repository (or copy the dc3 directory)
cd dc3
# Configure the build
cmake -B build -S . -DCMAKE_BUILD_TYPE=Release
# Build the library and tests
cmake --build build
# Run tests
cd build && ctestTo install the library to your system (requires root permissions for default paths):
sudo cmake --install buildThis will install:
- Headers to
${CMAKE_INSTALL_PREFIX}/include/dc3/ - Library to
${CMAKE_INSTALL_PREFIX}/lib/ - CMake config files to
${CMAKE_INSTALL_PREFIX}/lib/cmake/dc3/
Other projects can then use it via:
find_package(dc3 REQUIRED)
target_link_libraries(my_target PRIVATE dc3::dc3)A microbenchmark is included to compare the performance of the DC3 algorithm against a naive suffix array construction.
To build and run the benchmark:
# Configure and build (ensure BUILD_TESTING is ON, which is the default)
cmake -B build -S . -DCMAKE_BUILD_TYPE=Release
cmake --build build
# Run the benchmark with default settings (tests sizes from 16KB to 8MB)
# Note: Naive O(N^2 log N) algorithm is automatically skipped for large sizes.
./build/dc3_benchmark
# Run a quick verification (up to 256KB)
./build/dc3_benchmark --quick
# Run with custom limits (e.g., limit max size to 64KB to keep it fast)
./build/dc3_benchmark --max_bytes=65536The following is an example output of dc3_benchmark (up to 64KB) run on a host with the following specifications:
- CPU: AMD EPYC 7B13 (Base 2.25 GHz, Boost 3.5 GHz, 64 vCPUs)
- CPU Cache: 32 KB L1d per core, 512 KB L2 per core, 128 MB L3 (32 MB shared per 8-core CCX) (Note: For 64KB runs, the active working set fits entirely within the L2/L3 cache, so RAM speed does not affect these results.)
==========================================================
1. Random Corpus Microbenchmark
==========================================================
Size Alpha DC3 Time Naive Time Speedup
----------------------------------------------------------
16 KB 1 4.736 ms 0.113 s 23.9x
16 KB 2 3.321 ms 3.495 ms 1.1x
16 KB 4 3.064 ms 3.446 ms 1.1x
16 KB 8 2.494 ms 3.473 ms 1.4x
16 KB 16 2.627 ms 3.749 ms 1.4x
16 KB 32 2.605 ms 3.482 ms 1.3x
64 KB 1 12.607 ms 1.586 s 125.8x
64 KB 2 14.971 ms 16.004 ms 1.1x
64 KB 4 13.871 ms 15.362 ms 1.1x
64 KB 8 13.620 ms 15.663 ms 1.1x
64 KB 16 12.096 ms 15.436 ms 1.3x
64 KB 32 12.777 ms 16.047 ms 1.3x
----------------------------------------------------------
==========================================================
2. Canonical Pathological Repeats Corpus
Highlights extreme O(N^2 log N) degradation of naive
sorting on repetitive structures.
==========================================================
Size Pattern DC3 Time Naive Time Speedup
----------------------------------------------------------
16 KB Single_Char 2.923 ms 91.397 ms 31.3x
16 KB Scanned_Form 2.771 ms 58.039 ms 20.9x
64 KB Single_Char 11.971 ms 1.577 s 131.7x
64 KB Scanned_Form 12.471 ms 1.057 s 84.8x
----------------------------------------------------------
==========================================================
3. Multi-Pass OCR & Repetitive Document Alignment
Simulates aligning K scan passes of structured boilerplate
with realistic OCR errors.
==========================================================
Size OCR Err DC3 Time Naive Time Speedup
----------------------------------------------------------
16 KB 0.0010% 3.821 ms 13.811 ms 3.6x
16 KB 0.0100% 3.663 ms 10.562 ms 2.9x
16 KB 2.0000% 3.596 ms 4.486 ms 1.2x
64 KB 0.0010% 14.801 ms 0.139 s 9.4x
64 KB 0.0100% 15.486 ms 64.928 ms 4.2x
64 KB 2.0000% 15.408 ms 19.525 ms 1.3x
----------------------------------------------------------