When two text fragments are stitched together, the end of the first may already contain the start of the second. Write overlap(a, b) that returns the length of the longest suffix of a that is also a prefix of b. The overlap may be as long as the shorter string. Return 0 if there is none.
Examples
Input: a = "abcde", b = "cdefg"
Output: 3
Explanation: "cde" ends a and starts b.
Input: a = "aaa", b = "aaaa"
Output: 3
Input: a = "abc", b = "xyz"
Output: 0
Constraints
0 <= len(a), len(b) <= 5000, printable ASCII- Target: O(n * m) worst case is acceptable; aim for the longest overlap, not the first
Goals
- Compare a suffix of one string with a prefix of another
- Search candidate lengths in the right order
- Handle strings of different lengths