pub fn diff_onepass(r: &[u8], v: &[u8], opts: &DiffOptions) -> Vec<Command>Expand description
One-Pass algorithm (Section 4.1, Figure 3).
Scans R and V concurrently with two hash tables (one per string). Each table stores at most one offset per footprint (retain-existing policy: first entry wins, later collisions are discarded). Hash tables are logically flushed after each match via version counter (next-match policy). Time: O(np + q), space: O(q) — both constant for fixed p, q (Section 4.2). Suboptimal on transpositions: cannot match blocks that appear in different order between R and V (Section 4.3).
The hash table is auto-sized to max(q, num_seeds / p) so that large inputs get one slot per seed-length chunk of R. TABLE_SIZE acts as a floor for small files.