lcsLiftSuffix computes LCS(a, b[j:]) for each j = 0..len(b). It reverses both sequences, runs the standard forward DP, then maps the result back. Uses O(len(b)) space.
(a, b []string)
| 152 | // It reverses both sequences, runs the standard forward DP, then |
| 153 | // maps the result back. Uses O(len(b)) space. |
| 154 | func lcsLiftSuffix(a, b []string) []int { |
| 155 | ra := reverseStrings(a) |
| 156 | rb := reverseStrings(b) |
| 157 | |
| 158 | // row[j] = LCS(ra, rb[:j]) = LCS(a, b[len(b)-j:]) |
| 159 | row := lcsLift(ra, rb) |
| 160 | |
| 161 | // backward[j] = LCS(a, b[j:]) = row[len(b)-j] |
| 162 | result := make([]int, len(b)+1) |
| 163 | for j := 0; j <= len(b); j++ { |
| 164 | result[j] = row[len(b)-j] |
| 165 | } |
| 166 | return result |
| 167 | } |
| 168 | |
| 169 | func reverseStrings(s []string) []string { |
| 170 | result := make([]string, len(s)) |
no test coverage detected