Implement longest_common_substring(a: str, b: str) -> int: the length of the longest string that appears contiguously in both a and b.
longest_common_substring("placard", "backyard") # 3 "ard"
longest_common_substring("abcde", "xbcdy") # 3 "bcd"
longest_common_substring("abc", "xyz") # 0
This is not the longest common subsequence: the characters must sit next to each other in both strings. "abc" and "axbxc" share only runs of length 1.
Constraints: 0 <= len(a), len(b) <= 1000, any characters. Either string may be empty.
Show hint
let run[i][j] be the length of the common run that ends exactly at a[i-1] and b[j-1]: it is run[i-1][j-1] + 1 when those characters match and 0 otherwise, and the answer is the largest value anywhere in the table (not the bottom-right cell).