Suffix Arrays and Longest Common Prefix (LCP) arrays are among the most efficient algorithms for detecting repeated substrings within very large sequences. Originally developed for string processing, text indexing, and bioinformatics, these algorithms have become equally valuable in modern Large Language Model (LLM) data pipelines, particularly for identifying duplicated code blocks, boilerplate implementations, generated source code, and repeated programming patterns. Unlike document-level deduplication algorithms such as MinHash LSH, which estimate similarity between entire documents, Suffix Arrays operate at the substring level, allowing them to identify duplicated regions even when the surrounding files are completely different.
This distinction is particularly important for source code. Large software repositories frequently contain copied utility functions, repeated license headers, generated serialization code, template implementations, macro expansions, and partially duplicated methods. These duplicated regions may occupy only a small fraction of the overall file, making document-level similarity insufficient for identifying them. Detecting these shared fragments requires an algorithm capable of finding long common token sequences across millions of code chunks.
The Suffix Array provides exactly this capability. By sorting every suffix of a token sequence into lexicographic order, the algorithm places similar substrings adjacent to one another. The accompanying Longest Common Prefix array then measures how many consecutive tokens neighboring suffixes share. Long repeated code fragments therefore become immediately visible as large LCP values without requiring exhaustive pairwise comparison between every possible substring.
Unlike probabilistic algorithms such as MinHash, Suffix Arrays perform exact substring matching. Every duplicated token sequence discovered by the algorithm is guaranteed to exist within the original corpus, making the method particularly valuable when exact clone detection is required for training data cleaning, boilerplate removal, plagiarism analysis, cache optimization, and repository indexing.
Modern software development encourages code reuse. Developers frequently copy utility functions, adapt existing implementations, duplicate configuration templates, reuse generated code, and maintain similar implementations across multiple repositories. Consequently, large code corpora contain not only duplicated files but also thousands of partially duplicated code fragments embedded within otherwise unrelated projects.
These repeated fragments introduce several challenges for language model training. Repeated implementations increase memorization, reduce corpus diversity, and bias optimization toward frequently occurring boilerplate rather than genuinely informative programming patterns. Furthermore, duplicated code inflates storage requirements and preprocessing costs while contributing relatively little additional knowledge to the model.
A naïve solution would compare every substring within every file against every substring in every other file. Unfortunately, the number of possible substrings grows quadratically with document length, making exhaustive comparison computationally infeasible for datasets containing billions of tokens.
Suffix Arrays solve this problem by transforming substring comparison into a sorting problem. Instead of comparing substrings individually, the algorithm sorts every suffix exactly once. Once sorted, similar substrings automatically become adjacent within the suffix array, allowing duplicate detection to proceed through a simple linear scan of the accompanying LCP array. This transformation reduces computational complexity dramatically while preserving exact matching accuracy.
References
Manber, U., & Myers, G.Suffix Arrays: A New Method for On-Line String Searches.
Kasai, T., et al.Linear-Time Longest-Common-Prefix Computation in Suffix Arrays.
Gusfield, D.Algorithms on Strings, Trees, and Sequences.
FUNCTION construct_suffix_array_via_prefix_doubling(concatenated_token_sequence): total_sequence_length = length(concatenated_token_sequence) suffix_rank_array = BUILD_ARRAY_OF_SIZE(total_sequence_length) suffix_index_array = BUILD_ARRAY_OF_SIZE(total_sequence_length) FOR position_index IN RANGE(0, total_sequence_length): suffix_rank_array[position_index] = ordinal_value(concatenated_token_sequence[position_index]) suffix_index_array[position_index] = position_index comparison_offset = 1 WHILE comparison_offset < total_sequence_length: FUNCTION compare_suffixes_by_current_rank_pair(first_position, second_position): first_primary_rank = suffix_rank_array[first_position] second_primary_rank = suffix_rank_array[second_position] IF first_primary_rank != second_primary_rank: RETURN first_primary_rank - second_primary_rank first_secondary_rank = get_rank_or_negative_infinity(suffix_rank_array, first_position + comparison_offset, total_sequence_length) second_secondary_rank = get_rank_or_negative_infinity(suffix_rank_array, second_position + comparison_offset, total_sequence_length) RETURN first_secondary_rank - second_secondary_rank suffix_index_array = sort_array_using_comparator(suffix_index_array, compare_suffixes_by_current_rank_pair) updated_rank_array = BUILD_ARRAY_OF_SIZE(total_sequence_length) updated_rank_array[suffix_index_array[0]] = 0 FOR array_position IN RANGE(1, total_sequence_length): previous_suffix_position = suffix_index_array[array_position - 1] current_suffix_position = suffix_index_array[array_position] ranks_are_identical = (compare_suffixes_by_current_rank_pair(previous_suffix_position, current_suffix_position) == 0) IF ranks_are_identical: updated_rank_array[current_suffix_position] = updated_rank_array[previous_suffix_position] ELSE: updated_rank_array[current_suffix_position] = updated_rank_array[previous_suffix_position] + 1 suffix_rank_array = updated_rank_array IF suffix_rank_array[suffix_index_array[total_sequence_length - 1]] == total_sequence_length - 1: BREAK comparison_offset = comparison_offset * 2 RETURN suffix_index_array
The first stage of the algorithm transforms the complete token sequence into a Suffix Array. A suffix is simply the portion of the sequence beginning at a particular token position and extending to the end of the document. If a token sequence contains n positions, then exactly n suffixes exist. Rather than storing the suffixes themselves, the algorithm stores only their starting positions, significantly reducing memory consumption.
The construction algorithm sorts these suffixes according to lexicographic order. As a result, suffixes beginning with similar token sequences naturally become neighbors within the sorted array. This property is fundamental because duplicated substrings always appear as common prefixes of neighboring suffixes after sorting.
Modern implementations rarely perform explicit string sorting. Instead, specialized linear-time algorithms such as SA-IS or DC3 (Difference Cover Modulo 3) exploit recursive partitioning and induced sorting to construct suffix arrays efficiently even for extremely large token sequences. These algorithms avoid repeated substring comparisons by organizing suffixes through progressively refined ordering relationships.
The completed suffix array therefore functions as a searchable index over every possible suffix contained within the corpus. Subsequent stages of the algorithm rely entirely upon this sorted ordering rather than the original document organization.
References
Nong, G., Zhang, S., & Chan, W. H.Linear Suffix Array Construction by Almost Pure Induced Sorting.
Kärkkäinen, J., & Sanders, P.Simple Linear Work Suffix Array Construction.
FUNCTION construct_lcp_array_via_kasai_algorithm(concatenated_token_sequence, suffix_index_array): total_sequence_length = length(concatenated_token_sequence) inverse_suffix_index_array = BUILD_ARRAY_OF_SIZE(total_sequence_length) FOR array_position IN RANGE(0, total_sequence_length): inverse_suffix_index_array[suffix_index_array[array_position]] = array_position longest_common_prefix_array = BUILD_ARRAY_OF_SIZE(total_sequence_length, fill_value = 0) running_common_prefix_length = 0 FOR original_position IN RANGE(0, total_sequence_length): IF inverse_suffix_index_array[original_position] == total_sequence_length - 1: running_common_prefix_length = 0 CONTINUE adjacent_suffix_position = suffix_index_array[inverse_suffix_index_array[original_position] + 1] WHILE (original_position + running_common_prefix_length < total_sequence_length) AND (adjacent_suffix_position + running_common_prefix_length < total_sequence_length) AND (concatenated_token_sequence[original_position + running_common_prefix_length] == concatenated_token_sequence[adjacent_suffix_position + running_common_prefix_length]): running_common_prefix_length = running_common_prefix_length + 1 longest_common_prefix_array[inverse_suffix_index_array[original_position]] = running_common_prefix_length IF running_common_prefix_length > 0: running_common_prefix_length = running_common_prefix_length - 1 RETURN longest_common_prefix_array
Although the suffix array identifies neighboring suffixes, it does not directly reveal how similar those suffixes actually are. This information is computed by the Longest Common Prefix array. For every neighboring pair of suffixes within the sorted suffix array, the LCP array records the number of consecutive tokens shared before the two suffixes diverge.
The Kasai algorithm constructs the LCP array efficiently by exploiting relationships between adjacent suffixes. Instead of repeatedly comparing every suffix from the beginning, the algorithm reuses information computed during previous comparisons. Because neighboring suffixes frequently overlap substantially, the algorithm avoids redundant work by carrying forward the previously matched prefix length whenever possible.
Internally, the algorithm first constructs an inverse permutation known as the rank array. This structure maps every suffix position back to its location within the sorted suffix array, allowing constant-time identification of neighboring suffixes. Using this mapping, the algorithm performs only incremental comparisons while progressively updating the current common prefix length. This optimization enables linear-time LCP construction despite the potentially enormous number of suffixes involved.
The resulting LCP array transforms the suffix array from a sorted index into a powerful duplicate detection structure. Large LCP values immediately indicate long repeated token sequences shared between neighboring suffixes.
References
Kasai, T., et al.Linear-Time Longest-Common-Prefix Computation in Suffix Arrays.
Gusfield, D.Algorithms on Strings, Trees, and Sequences.
FUNCTION detect_cross_chunk_clone_regions(concatenated_token_sequence, suffix_index_array, longest_common_prefix_array, chunk_boundary_lookup_table, minimum_clone_token_length): total_sequence_length = length(concatenated_token_sequence) raw_clone_region_list = EMPTY_LIST() array_position = 1 WHILE array_position < total_sequence_length: IF longest_common_prefix_array[array_position] < minimum_clone_token_length: array_position = array_position + 1 CONTINUE matching_group_start_index = array_position - 1 matching_group_end_index = array_position WHILE matching_group_end_index < total_sequence_length AND longest_common_prefix_array[matching_group_end_index] >= minimum_clone_token_length: matching_group_end_index = matching_group_end_index + 1 shared_common_prefix_length_for_group = MINIMUM_OVER_RANGE(longest_common_prefix_array, matching_group_start_index + 1, matching_group_end_index) suffix_positions_in_group = suffix_index_array[matching_group_start_index : matching_group_end_index + 1] FOR first_group_index IN RANGE(0, length(suffix_positions_in_group)): FOR second_group_index IN RANGE(first_group_index + 1, length(suffix_positions_in_group)): first_suffix_start_position = suffix_positions_in_group[first_group_index] second_suffix_start_position = suffix_positions_in_group[second_group_index] first_originating_chunk = lookup_chunk_for_position(chunk_boundary_lookup_table, first_suffix_start_position) second_originating_chunk = lookup_chunk_for_position(chunk_boundary_lookup_table, second_suffix_start_position) IF first_originating_chunk == second_originating_chunk: CONTINUE raw_clone_region = BUILD_RAW_CLONE_REGION( first_chunk_identifier = first_originating_chunk, first_start_position = first_suffix_start_position, second_chunk_identifier = second_originating_chunk, second_start_position = second_suffix_start_position, shared_token_length = shared_common_prefix_length_for_group ) APPEND(raw_clone_region_list, raw_clone_region) array_position = matching_group_end_index RETURN raw_clone_region_list
Real-world code repositories consist of many independent files rather than one continuous token sequence. To enable clone detection across multiple chunks, the algorithm concatenates every chunk into a single token array while inserting unique sentinel separators between consecutive chunks. These sentinel tokens guarantee that suffixes cannot incorrectly extend across chunk boundaries, preserving the integrity of individual documents.
Once the unified token sequence has been constructed, the suffix array and LCP array are generated exactly as they would be for a single document. The algorithm then scans the LCP array sequentially. Whenever neighboring suffixes share a common prefix whose length exceeds a predefined threshold, the corresponding token regions become candidate code clones.
Each suffix position must then be mapped back to its originating chunk. Rather than storing explicit document identifiers for every token, the algorithm maintains a sorted list of chunk boundaries. A binary search over these boundaries efficiently determines which original chunk contains each suffix position, allowing duplicated regions to be associated with their source files.
This mapping stage converts low-level token offsets into meaningful clone relationships between code chunks. Rather than merely reporting repeated substrings, the algorithm identifies precisely which files share duplicated implementations and where those implementations begin.
References
Manber, U., & Myers, G.Suffix Arrays: A New Method for On-Line String Searches.
Gusfield, D.Algorithms on Strings, Trees, and Sequences.
FUNCTION construct_and_resolve_clone_pairs(raw_clone_region_list, minimum_clone_token_length): normalized_clone_region_list = EMPTY_LIST() FOR EACH raw_clone_region IN raw_clone_region_list: normalized_region = normalize_pair_ordering(raw_clone_region, ORDER_BY = (first_chunk_identifier, first_start_position)) APPEND(normalized_clone_region_list, normalized_region) normalized_clone_region_list = sort_by_chunk_pair_then_start_position(normalized_clone_region_list) merged_clone_pair_list = EMPTY_LIST() current_merged_region = NULL FOR EACH normalized_region IN normalized_clone_region_list: IF current_merged_region == NULL: current_merged_region = normalized_region CONTINUE SAME_CHUNK_PAIR = (normalized_region.first_chunk_identifier == current_merged_region.first_chunk_identifier) AND (normalized_region.second_chunk_identifier == current_merged_region.second_chunk_identifier) FIRST_REGION_OVERLAPS = normalized_region.first_start_position <= (current_merged_region.first_start_position + current_merged_region.shared_token_length) SECOND_REGION_OVERLAPS = normalized_region.second_start_position <= (current_merged_region.second_start_position + current_merged_region.shared_token_length) IF SAME_CHUNK_PAIR AND FIRST_REGION_OVERLAPS AND SECOND_REGION_OVERLAPS: merged_first_end = MAXIMUM(current_merged_region.first_start_position + current_merged_region.shared_token_length, normalized_region.first_start_position + normalized_region.shared_token_length) merged_second_end = MAXIMUM(current_merged_region.second_start_position + current_merged_region.shared_token_length, normalized_region.second_start_position + normalized_region.shared_token_length) current_merged_region.shared_token_length = merged_first_end - current_merged_region.first_start_position ELSE: APPEND(merged_clone_pair_list, current_merged_region) current_merged_region = normalized_region IF current_merged_region != NULL: APPEND(merged_clone_pair_list, current_merged_region) final_clone_pair_list = EMPTY_LIST() FOR EACH merged_region IN merged_clone_pair_list: IF merged_region.shared_token_length < minimum_clone_token_length: CONTINUE clone_pair = BUILD_CLONE_PAIR_OBJECT( first_chunk_identifier = merged_region.first_chunk_identifier, first_token_range = BUILD_RANGE(merged_region.first_start_position, merged_region.first_start_position + merged_region.shared_token_length), second_chunk_identifier = merged_region.second_chunk_identifier, second_token_range = BUILD_RANGE(merged_region.second_start_position, merged_region.second_start_position + merged_region.shared_token_length), cloned_token_length = merged_region.shared_token_length ) APPEND(final_clone_pair_list, clone_pair) RETURN final_clone_pair_list
Every sufficiently large LCP value represents a duplicated substring, but multiple neighboring suffixes frequently describe overlapping regions of the same clone. Reporting every individual match would therefore produce many redundant clone pairs describing essentially identical duplicated code.
To eliminate this redundancy, the algorithm groups overlapping matches into unified clone regions. Adjacent duplicate intervals sharing substantial overlap are merged into a single clone representation describing the complete duplicated block rather than numerous fragmented matches. This consolidation significantly improves both storage efficiency and interpretability while preserving all meaningful clone information.
The resulting clone pairs record the originating chunks, the starting offsets within each chunk, and the length of the duplicated token sequence. These records provide the foundation for downstream processing, including dataset deduplication, boilerplate removal, repository analysis, cache optimization, plagiarism detection, and retrieval acceleration.
One important advantage of Suffix Array–based clone detection is that every reported duplicate corresponds to an exact shared token sequence. Unlike probabilistic similarity algorithms, no statistical approximation is involved. The detected clone is guaranteed to exist exactly as reported within both source locations. This deterministic behavior makes Suffix Arrays particularly valuable whenever precise clone localization is required.
References
Baker, B. S.On Finding Duplication and Near-Duplication in Large Software Systems.
Kamiya, T., Kusumoto, S., & Inoue, K.CCFinder: A Multilinguistic Token-Based Code Clone Detection System.
Gusfield, D.Algorithms on Strings, Trees, and Sequences.
name: suffix_array_lcp_code_clone_detection_pipelineon: chunk_collection_ready_trigger: description: Fires once a full set of code chunks (e.g. from AST-based chunking) is ready to be scanned for clonesenv: minimum_clone_token_length: shortest shared token run that counts as a real clone, filters out trivial matches like single tokens or short syntax fragments unique_chunk_separator_token: sentinel inserted between chunks in the concatenated sequence, guaranteed to not occur in any real token streamjobs: stage_1_concatenate_chunks_with_separators: description: Join every chunk's token sequence into one long sequence, with unique separator tokens marking chunk boundaries depends_on: none, entry point for chunk_collection_ready_trigger inputs: chunk_collection: list of chunks, each with a token_sequence and chunk_identifier steps: - id: build_concatenated_sequence_and_boundary_table run: FOR EACH chunk IN chunk_collection → append token_sequence, append unique_chunk_separator_token, record start/end positions loop_type: fixed-count iteration over the chunk collection why_separators_are_required_and_not_optional: > Without a separator, a suffix from the tail of one chunk could naturally continue into the head of the next chunk's tokens, since they are physically adjacent in the concatenated array. This would let the suffix array treat token runs that cross a chunk boundary as if they were a real match, when they are actually two unrelated chunks placed next to each other by construction, not by content similarity. why_each_separator_must_be_unique_per_chunk_and_not_a_single_shared_symbol: > If every chunk used the same separator symbol, a suffix starting exactly at a separator in chunk A would appear identical to a suffix starting at a separator in chunk B, since both begin with the same symbol. A single shared separator would therefore itself become a spurious "clone" detected between every pair of chunks. A unique separator per chunk guarantees no two separators ever match each other. outputs: concatenated_token_sequence: single token array representing the entire chunk collection chunk_boundary_lookup_table: mapping from any position in the concatenated sequence back to its originating chunk_identifier stage_2_suffix_array_construction: description: Build an array of all suffix starting positions, sorted lexicographically by suffix content depends_on: stage_1_concatenate_chunks_with_separators inputs: concatenated_token_sequence: from stage_1 steps: - id: initialize_ranks_from_single_tokens run: FOR position_index IN RANGE(0, total_sequence_length) → suffix_rank_array[position_index] = ordinal_value of that single token - id: prefix_doubling_loop run: WHILE comparison_offset < total_sequence_length → sort suffixes by (current_rank, rank_at_offset), reassign compressed ranks, double comparison_offset loop_type: doubling loop, exponentially growing comparison window, not a fixed-count loop why_prefix_doubling_and_not_naive_full_suffix_comparison: > Naively comparing full suffixes against each other to sort them would cost time proportional to sequence length for every single comparison, compounding into a very expensive total sort. Prefix doubling instead sorts suffixes by their first 1 token, then effectively by their first 2 tokens (using the previous round's ranks as a shortcut), then first 4, then first 8, and so on, reusing all prior work at each step instead of re-scanning full suffixes from scratch every round. why_the_loop_terminates_when_ranks_become_fully_unique: > Once every suffix has a distinct rank, all suffixes are already fully and correctly ordered relative to each other; continuing to double the comparison offset past this point would do identical, wasted work, since no further comparisons could change the already-unique ordering. effect_on_downstream_if_this_stage_is_wrong: > The entire rest of the pipeline treats adjacency in suffix_index_array as a proxy for content similarity. Any error in the sort here means truly similar suffixes may end up far apart in the array, making them invisible to stage_4's adjacent-only scanning regardless of how correct stage_3 and stage_4 are individually. outputs: suffix_index_array: array of starting positions, ordered so that adjacent entries correspond to lexicographically adjacent suffixes stage_3_lcp_array_construction: description: For each adjacent pair of suffixes in sorted order, compute how many leading tokens they share depends_on: stage_2_suffix_array_construction inputs: concatenated_token_sequence: from stage_1 suffix_index_array: from stage_2 steps: - id: build_inverse_suffix_index run: FOR array_position IN RANGE(0, total_sequence_length) → inverse_suffix_index_array[suffix_index_array[array_position]] = array_position why_the_inverse_index_is_needed: > Kasai's algorithm processes suffixes in original document order for efficiency reasons explained below, but needs to know each suffix's position in the sorted suffix array to know where to write its LCP value. The inverse index provides that lookup in constant time instead of a linear search per suffix. - id: kasai_linear_scan_with_shrinking_reuse run: FOR original_position IN RANGE(0, total_sequence_length) → extend running_common_prefix_length from previous suffix's leftover match, decrement by at most one per step loop_type: single linear scan with a bounded-decrement invariant, not a fresh comparison from zero each time why_processing_in_original_order_and_not_sorted_order: > Kasai's key insight is that the suffix starting at position i+1 in the original sequence shares at least (running_common_prefix_length - 1) tokens with its own sorted-order neighbor, because removing the first token from two suffixes that matched for L tokens leaves suffixes that still match for at least L-1 tokens. This reuse is only available when moving through original positions in order; processing in sorted order would discard this relationship and force a full recomparison from scratch at every single position. why_this_gives_linear_time_instead_of_quadratic: > Because running_common_prefix_length only ever decreases by at most one per step before the inner comparison loop resumes extending it, the total number of comparison operations across the entire scan is bounded by twice the sequence length, rather than by sequence length multiplied by average match length. outputs: longest_common_prefix_array: array where entry at sorted position p gives the shared prefix length between the suffixes at sorted positions p-1 and p stage_4_cross_chunk_clone_region_detection: description: Scan the sorted suffixes for runs of high LCP values, then filter matches down to only those spanning two different chunks depends_on: stage_3_lcp_array_construction, stage_1_concatenate_chunks_with_separators inputs: suffix_index_array: from stage_2 longest_common_prefix_array: from stage_3 chunk_boundary_lookup_table: from stage_1 minimum_clone_token_length: from env steps: - id: group_consecutive_high_lcp_entries run: WHILE array_position < total_sequence_length → extend matching_group_end_index while longest_common_prefix_array stays at or above minimum_clone_token_length loop_type: sequential scan with a variable-width grouping condition why_grouping_and_not_comparing_only_immediate_neighbors: > A run of three or more suffixes can all share the same long common prefix with each other, not just with their immediate sorted neighbor. Only checking immediate pairs (LCP array entries one at a time in isolation) would miss matches between suffixes that are two or more positions apart in the sorted array but still share the full run's common prefix. why_the_threshold_check_uses_minimum_clone_token_length_here_too: > This is the same threshold used later in stage_5's final filter, applied early as a pruning step. Grouping only regions that already meet the minimum length avoids wasting the expensive pairwise chunk-comparison work in the next step on short, uninteresting matches that would be discarded anyway. - id: pairwise_chunk_origin_check_within_group run: FOR first_group_index → FOR second_group_index > first_group_index → look up originating chunk for each suffix start position, keep pair only if chunks differ loop_type: nested loop over all pairs within a matching group, not just adjacent entries why_all_pairs_within_the_group_and_not_just_consecutive_ones: > Any two suffixes within the same high-LCP group share at least the group's common prefix length with each other, by construction. Only checking consecutive pairs would miss valid cross-chunk clone pairs where the two matching suffixes are not directly adjacent in the sorted array but are still both within the same group. why_same_chunk_pairs_are_discarded_here: > A long repeated pattern within a single chunk (e.g. a loop body duplicated by hand inside one function) is a within-chunk repetition concern, not a cross-chunk clone. This pipeline is specifically scoped to detecting duplication between different chunks, so same-chunk matches are filtered out at the earliest point they can be identified, rather than being carried forward and filtered later. outputs: raw_clone_region_list: unmerged, potentially overlapping list of cross-chunk matching regions, each with two positions and a shared token length stage_5_clone_pair_construction_and_overlap_resolution: description: Normalize, sort, and merge overlapping raw clone regions into final non-redundant clone pairs depends_on: stage_4_cross_chunk_clone_region_detection inputs: raw_clone_region_list: from stage_4 minimum_clone_token_length: from env steps: - id: normalize_and_sort run: normalize each region's ordering, sort by (first_chunk_identifier, first_start_position) why_normalization_is_needed: > Because stage_4's nested loop can discover the same underlying pair of chunks in either order depending on which suffix appeared first in the group, without normalizing to a consistent (first_chunk, second_chunk) ordering, the same real clone could appear twice in the list as two superficially different entries, confusing the merge step that follows. - id: sequential_merge_of_overlapping_regions run: FOR EACH normalized_region → merge into current_merged_region if same chunk pair and both positions overlap, otherwise close out current_merged_region and start a new one loop_type: sequential accumulation with a merge-or-flush condition, relies on the prior sort step for correctness why_overlap_merging_is_necessary_at_all: > A single real clone spanning many tokens can be broken into several overlapping raw_clone_region entries by stage_4, because multiple different suffix starting positions within that same clone all independently satisfy the minimum_clone_token_length grouping condition. Without merging, one real clone would be reported as many fragmented, overlapping "clones," inflating clone counts and confusing any downstream consumer trying to count or visualize actual duplication. why_this_depends_on_the_sort_from_the_previous_step: > The sequential merge only correctly catches overlaps between consecutive entries in the list. If entries were not sorted by chunk pair and position first, two overlapping regions could end up far apart in list order and never be compared against each other at all, leaving the fragmentation unresolved. - id: final_length_filter run: IF merged_region.shared_token_length < minimum_clone_token_length THEN discard why_a_second_filter_after_merging_and_not_relying_on_stage_4s_filter_alone: > This check exists for symmetry and safety, not because merging can shrink a region below threshold in the current merge logic; it guards against any merged region construction path that could theoretically produce a shorter combined length than expected, ensuring the threshold contract is enforced at the pipeline's actual exit point, not only at an intermediate step. outputs: final_clone_pair_list: clean, non-overlapping list of cross-chunk clone pairs, each with concrete token ranges in both chunks, ready for reporting or downstream refactoring tools
critical_dependency_chain: stage_1_separator_uniqueness: controls: whether any match found later is even a legitimate content match versus a boundary artifact if_this_breaks: stage_4 either misses real cross-chunk clones near boundaries (over-broken sequence) or reports every chunk as cloned with every other chunk (shared separator symbol treated as matching content) stage_2_suffix_sort_correctness: controls: whether stage_3's Kasai algorithm produces valid LCP values at all, since Kasai assumes a correctly sorted suffix_index_array as a precondition if_this_breaks: longest_common_prefix_array becomes meaningless, and every downstream stage operates on incorrect data without any explicit error being raised stage_3_lcp_correctness: controls: exactly which suffix groups stage_4 considers as candidate matches if_this_breaks: real clones produce LCP values that don't cross minimum_clone_token_length and are silently skipped, or unrelated suffixes appear to match and get carried forward as false clones stage_4_same_chunk_filtering: controls: whether the pipeline's output is actually about cross-chunk duplication or gets polluted with within-chunk repetition if_this_breaks: the final clone report mixes two conceptually different phenomena, within-file loops or repeated patterns versus real duplication across separate chunks, making the output unusable for a cross-chunk-specific refactoring or deduplication decision stage_5_overlap_merge_correctness: controls: whether one real clone is reported once, or reported as many fragmented overlapping entries if_this_breaks: clone counts and total duplicated-token statistics become inflated and unreliable, even though the underlying detected positions in stage_4 were individually correct
Suffix Arrays and Longest Common Prefix (LCP) arrays offer a deterministic and computationally efficient solution for exact code clone detection in large-scale software repositories. Unlike document-level similarity methods, they identify duplicated code at the substring level, enabling precise localization of repeated implementations even when they appear within otherwise unrelated files.
The algorithm transforms the expensive problem of exhaustive substring comparison into an efficient sequence of suffix sorting, LCP computation, and linear scanning. This enables scalable detection of duplicated code fragments while preserving exact matching guarantees. By mapping detected duplicates back to their original source files and consolidating overlapping matches, the approach produces meaningful clone groups suitable for downstream analysis.
As modern software repositories continue to expand and AI systems increasingly rely on high-quality training corpora, exact clone detection remains an essential preprocessing step. Suffix Arrays combined with LCP provide a robust foundation for repository deduplication, boilerplate removal, plagiarism detection, retrieval optimization, and improving the diversity and quality of datasets used by large language models. Their combination of theoretical efficiency, deterministic accuracy, and scalability has established them as one of the fundamental algorithms for large-scale code analysis and preprocessing.
Suffix Array + Longest Common Prefix (LCP) for Code Clone Detection was originally published in Stackademic on Medium, where people are continuing the conversation by highlighting and responding to this story.