Find longest matching block in a[alo:ahi] and b[blo:bhi]. If IsJunk is not defined: Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where alo <= i <= i+k <= ahi blo <= j <= j+k <= bhi and for all (i',j',k') meeting those conditions, k >= k' i <= i' and if i == i', j <= j' In other
(alo, ahi, blo, bhi int)
| 268 | // |
| 269 | // If no blocks match, return (alo, blo, 0). |
| 270 | func (m *SequenceMatcher) findLongestMatch(alo, ahi, blo, bhi int) Match { |
| 271 | // CAUTION: stripping common prefix or suffix would be incorrect. |
| 272 | // E.g., |
| 273 | // ab |
| 274 | // acab |
| 275 | // Longest matching block is "ab", but if common prefix is |
| 276 | // stripped, it's "a" (tied with "b"). UNIX(tm) diff does so |
| 277 | // strip, so ends up claiming that ab is changed to acab by |
| 278 | // inserting "ca" in the middle. That's minimal but unintuitive: |
| 279 | // "it's obvious" that someone inserted "ac" at the front. |
| 280 | // Windiff ends up at the same place as diff, but by pairing up |
| 281 | // the unique 'b's and then matching the first two 'a's. |
| 282 | besti, bestj, bestsize := alo, blo, 0 |
| 283 | |
| 284 | // find longest junk-free match |
| 285 | // during an iteration of the loop, j2len[j] = length of longest |
| 286 | // junk-free match ending with a[i-1] and b[j] |
| 287 | N := bhi - blo |
| 288 | j2len := make([]int, N) |
| 289 | newj2len := make([]int, N) |
| 290 | var indices []int |
| 291 | for i := alo; i != ahi; i++ { |
| 292 | // look at all instances of a[i] in b; note that because |
| 293 | // b2j has no junk keys, the loop is skipped if a[i] is junk |
| 294 | newindices := m.b2j.get(m.a[i]) |
| 295 | for _, j := range newindices { |
| 296 | // a[i] matches b[j] |
| 297 | if j < blo { |
| 298 | continue |
| 299 | } |
| 300 | if j >= bhi { |
| 301 | break |
| 302 | } |
| 303 | k := 1 |
| 304 | if j > blo { |
| 305 | k = j2len[j-1-blo] + 1 |
| 306 | } |
| 307 | newj2len[j-blo] = k |
| 308 | if k > bestsize { |
| 309 | besti, bestj, bestsize = i-k+1, j-k+1, k |
| 310 | } |
| 311 | } |
| 312 | // j2len = newj2len, clear and reuse j2len as newj2len |
| 313 | for _, j := range indices { |
| 314 | if j < blo { |
| 315 | continue |
| 316 | } |
| 317 | if j >= bhi { |
| 318 | break |
| 319 | } |
| 320 | j2len[j-blo] = 0 |
| 321 | } |
| 322 | indices = newindices |
| 323 | j2len, newj2len = newj2len, j2len |
| 324 | } |
| 325 | |
| 326 | // Extend the best by non-junk elements on each end. In particular, |
| 327 | // "popular" non-junk elements aren't in b2j, which greatly speeds |
no test coverage detected