lcsLength computes the LCS length using the standard O(N*M) DP. Used only in tests to verify correctness.
(seq1, seq2 []string)
| 176 | // lcsLength computes the LCS length using the standard O(N*M) DP. |
| 177 | // Used only in tests to verify correctness. |
| 178 | func lcsLength(seq1, seq2 []string) int { |
| 179 | prev := make([]int, len(seq2)+1) |
| 180 | curr := make([]int, len(seq2)+1) |
| 181 | for i := 0; i < len(seq1); i++ { |
| 182 | for j := 0; j < len(seq2); j++ { |
| 183 | if seq1[i] == seq2[j] { |
| 184 | curr[j+1] = prev[j] + 1 |
| 185 | } else if prev[j+1] >= curr[j] { |
| 186 | curr[j+1] = prev[j+1] |
| 187 | } else { |
| 188 | curr[j+1] = curr[j] |
| 189 | } |
| 190 | } |
| 191 | prev, curr = curr, prev |
| 192 | for i := range curr { |
| 193 | curr[i] = 0 |
| 194 | } |
| 195 | } |
| 196 | return prev[len(seq2)] |
| 197 | } |
| 198 | |
| 199 | func generateRandomSequence(rnd *rand.Rand, length, alphabetSize int) []string { |
| 200 | result := make([]string, length) |
no outgoing calls
no test coverage detected