Find longest matching block in a[alo:ahi] and b[blo:bhi]. By default it will find the longest match in the entirety of a and b. 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 <
(self, alo=0, ahi=None, blo=0, bhi=None)
| 303 | del b2j[elt] |
| 304 | |
| 305 | def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None): |
| 306 | """Find longest matching block in a[alo:ahi] and b[blo:bhi]. |
| 307 | |
| 308 | By default it will find the longest match in the entirety of a and b. |
| 309 | |
| 310 | If isjunk is not defined: |
| 311 | |
| 312 | Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where |
| 313 | alo <= i <= i+k <= ahi |
| 314 | blo <= j <= j+k <= bhi |
| 315 | and for all (i',j',k') meeting those conditions, |
| 316 | k >= k' |
| 317 | i <= i' |
| 318 | and if i == i', j <= j' |
| 319 | |
| 320 | In other words, of all maximal matching blocks, return one that |
| 321 | starts earliest in a, and of all those maximal matching blocks that |
| 322 | start earliest in a, return the one that starts earliest in b. |
| 323 | |
| 324 | >>> s = SequenceMatcher(None, " abcd", "abcd abcd") |
| 325 | >>> s.find_longest_match(0, 5, 0, 9) |
| 326 | Match(a=0, b=4, size=5) |
| 327 | |
| 328 | If isjunk is defined, first the longest matching block is |
| 329 | determined as above, but with the additional restriction that no |
| 330 | junk element appears in the block. Then that block is extended as |
| 331 | far as possible by matching (only) junk elements on both sides. So |
| 332 | the resulting block never matches on junk except as identical junk |
| 333 | happens to be adjacent to an "interesting" match. |
| 334 | |
| 335 | Here's the same example as before, but considering blanks to be |
| 336 | junk. That prevents " abcd" from matching the " abcd" at the tail |
| 337 | end of the second sequence directly. Instead only the "abcd" can |
| 338 | match, and matches the leftmost "abcd" in the second sequence: |
| 339 | |
| 340 | >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd") |
| 341 | >>> s.find_longest_match(0, 5, 0, 9) |
| 342 | Match(a=1, b=0, size=4) |
| 343 | |
| 344 | If no blocks match, return (alo, blo, 0). |
| 345 | |
| 346 | >>> s = SequenceMatcher(None, "ab", "c") |
| 347 | >>> s.find_longest_match(0, 2, 0, 1) |
| 348 | Match(a=0, b=0, size=0) |
| 349 | """ |
| 350 | |
| 351 | # CAUTION: stripping common prefix or suffix would be incorrect. |
| 352 | # E.g., |
| 353 | # ab |
| 354 | # acab |
| 355 | # Longest matching block is "ab", but if common prefix is |
| 356 | # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so |
| 357 | # strip, so ends up claiming that ab is changed to acab by |
| 358 | # inserting "ca" in the middle. That's minimal but unintuitive: |
| 359 | # "it's obvious" that someone inserted "ac" at the front. |
| 360 | # Windiff ends up at the same place as diff, but by pairing up |
| 361 | # the unique 'b's and then matching the first two 'a's. |
| 362 |