Two Scribes, a Few Slips

Two scribes copied parts of the same old text; their copies are the strings a and b. You want to find a passage the two copies share, allowing for a few slips of the pen.

Choose a length L, a start i in a and a start j in b, and compare a[i:i + L] with b[j:j + L] letter by letter (first with first, second with second, and so on). The two passages match with at most k slips if they differ in at most k positions. Return the largest L for which such a pair of passages exists. (L = 0 always works.)

Examples

Input:  a = "GATTACA", b = "TTAGCAT", k = 1
Output: 4
Explanation: a[2:6] = "TTAC" and b[0:4] = "TTAG" differ only in the last letter.

Input:  a = "ACGT", b = "TGCA", k = 0
Output: 1

Input:  a = "AAAA", b = "CCCCCC", k = 2
Output: 2

Constraints

• 0 <= len(a), len(b) <= 1000
• a and b contain uppercase letters
• 0 <= k <= 1000
• Target complexity: O(len(a) · len(b)). Trying every pair of starts and extending each one is too slow for the largest tests.

Goals

• Reduce a two-string question to one window per alignment of the strings
• Run an at-most-k-mismatches window along each alignment