Significance:
Overlap graphs are the earliest and most intuitive model of genome assembly: if the suffix of one sequencing read matches the prefix of another, they probably come from adjacent regions of the genome. This "overlap-layout-consensus" (OLC) strategy was used by early assemblers (like the Celera Assembler for the human genome) before de Bruijn-graph approaches (Problem 18) became dominant for short-read data.
Statement
Given a collection of DNA strings (each with a unique ID) and an integer `k`, construct the **overlap graph**: for every ordered pair of distinct sequences `(A, B)`, add a directed edge `A → B` if the **length-k suffix** of `A` exactly equals the **length-k prefix** of `B`. Output every such edge, one per line, as `sourceID destinationID`. Order of output edges does not matter for grading (the judge should compare as a set).
Constraints
- `2 ≤ number of sequences ≤ 50` - `k ≤ min(length of all sequences)` - A sequence must not have an edge to itself even if it trivially overlaps itself
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...