lcsLift computes the last row of the standard LCS DP matrix. result[j] = LCS(a, b[:j]) for j = 0..len(b). Uses O(len(b)) space.
(a, b []string)
| 127 | // lcsLift computes the last row of the standard LCS DP matrix. |
| 128 | // result[j] = LCS(a, b[:j]) for j = 0..len(b). Uses O(len(b)) space. |
| 129 | func lcsLift(a, b []string) []int { |
| 130 | prev := make([]int, len(b)+1) |
| 131 | curr := make([]int, len(b)+1) |
| 132 | |
| 133 | for i := 0; i < len(a); i++ { |
| 134 | ai := a[i] |
| 135 | for j := 0; j < len(b); j++ { |
| 136 | if ai == b[j] { |
| 137 | curr[j+1] = prev[j] + 1 |
| 138 | } else if prev[j+1] >= curr[j] { |
| 139 | curr[j+1] = prev[j+1] |
| 140 | } else { |
| 141 | curr[j+1] = curr[j] |
| 142 | } |
| 143 | } |
| 144 | prev, curr = curr, prev |
| 145 | clearRow(curr) |
| 146 | } |
| 147 | |
| 148 | return prev |
| 149 | } |
| 150 | |
| 151 | // lcsLiftSuffix computes LCS(a, b[j:]) for each j = 0..len(b). |
| 152 | // It reverses both sequences, runs the standard forward DP, then |
no test coverage detected