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)
| 207 | // |
| 208 | // If no blocks match, return (alo, blo, 0). |
| 209 | func (m *SequenceMatcher) findLongestMatch(alo, ahi, blo, bhi int) Match { |
| 210 | // CAUTION: stripping common prefix or suffix would be incorrect. |
| 211 | // E.g., |
| 212 | // ab |
| 213 | // acab |
| 214 | // Longest matching block is "ab", but if common prefix is |
| 215 | // stripped, it's "a" (tied with "b"). UNIX(tm) diff does so |
| 216 | // strip, so ends up claiming that ab is changed to acab by |
| 217 | // inserting "ca" in the middle. That's minimal but unintuitive: |
| 218 | // "it's obvious" that someone inserted "ac" at the front. |
| 219 | // Windiff ends up at the same place as diff, but by pairing up |
| 220 | // the unique 'b's and then matching the first two 'a's. |
| 221 | besti, bestj, bestsize := alo, blo, 0 |
| 222 | |
| 223 | // find longest junk-free match |
| 224 | // during an iteration of the loop, j2len[j] = length of longest |
| 225 | // junk-free match ending with a[i-1] and b[j] |
| 226 | N := bhi - blo |
| 227 | j2len := make([]int, N) |
| 228 | newj2len := make([]int, N) |
| 229 | var indices []int |
| 230 | for i := alo; i != ahi; i++ { |
| 231 | // look at all instances of a[i] in b; note that because |
| 232 | // b2j has no junk keys, the loop is skipped if a[i] is junk |
| 233 | newindices := m.b2j[m.a[i]] |
| 234 | for _, j := range newindices { |
| 235 | // a[i] matches b[j] |
| 236 | if j < blo { |
| 237 | continue |
| 238 | } |
| 239 | if j >= bhi { |
| 240 | break |
| 241 | } |
| 242 | k := 1 |
| 243 | if j > blo { |
| 244 | k = j2len[j-1-blo] + 1 |
| 245 | } |
| 246 | newj2len[j-blo] = k |
| 247 | if k > bestsize { |
| 248 | besti, bestj, bestsize = i-k+1, j-k+1, k |
| 249 | } |
| 250 | } |
| 251 | // j2len = newj2len, clear and reuse j2len as newj2len |
| 252 | for _, j := range indices { |
| 253 | if j < blo { |
| 254 | continue |
| 255 | } |
| 256 | if j >= bhi { |
| 257 | break |
| 258 | } |
| 259 | j2len[j-blo] = 0 |
| 260 | } |
| 261 | indices = newindices |
| 262 | j2len, newj2len = newj2len, j2len |
| 263 | } |
| 264 | |
| 265 | // Extend the best by non-junk elements on each end. In particular, |
| 266 | // "popular" non-junk elements aren't in b2j, which greatly speeds |
no test coverage detected