Compute the Longest Common Subsequence using dynamic programming. Returns a list of matching positions in both sequences.
(old: &[Line<'a>], new: &[Line<'a>])
| 71 | /// |
| 72 | /// Returns a list of matching positions in both sequences. |
| 73 | fn compute_lcs<'a>(old: &[Line<'a>], new: &[Line<'a>]) -> Vec<LcsElement> { |
| 74 | let n = old.len(); |
| 75 | let m = new.len(); |
| 76 | |
| 77 | // Build DP table |
| 78 | // dp[i][j] = length of LCS of old[0..i] and new[0..j] |
| 79 | let mut dp = vec![vec![0usize; m + 1]; n + 1]; |
| 80 | |
| 81 | for i in 1..=n { |
| 82 | for j in 1..=m { |
| 83 | if old[i - 1] == new[j - 1] { |
| 84 | dp[i][j] = dp[i - 1][j - 1] + 1; |
| 85 | } else { |
| 86 | dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]); |
| 87 | } |
| 88 | } |
| 89 | } |
| 90 | |
| 91 | // Backtrack to find the actual LCS |
| 92 | let mut lcs = Vec::with_capacity(dp[n][m]); |
| 93 | let mut i = n; |
| 94 | let mut j = m; |
| 95 | |
| 96 | while i > 0 && j > 0 { |
| 97 | if old[i - 1] == new[j - 1] { |
| 98 | lcs.push(LcsElement { |
| 99 | old_idx: i - 1, |
| 100 | new_idx: j - 1, |
| 101 | }); |
| 102 | i -= 1; |
| 103 | j -= 1; |
| 104 | } else if dp[i - 1][j] > dp[i][j - 1] { |
| 105 | i -= 1; |
| 106 | } else { |
| 107 | j -= 1; |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | lcs.reverse(); |
| 112 | lcs |
| 113 | } |
| 114 | |
| 115 | /// Convert an LCS to diff operations. |
| 116 | fn lcs_to_diff(lcs: &[LcsElement], old_len: usize, new_len: usize) -> DiffResult { |