434. The Longest Shared Run
Print the length of the longest string that appears in BOTH inputs as a
CONTIGUOUS run of characters. Print 0 if they share nothing.
abcde and abfce -> 2 ab
banana and ananas -> 5 anana
Problem #237 finds the longest common SUBSEQUENCE, where characters may be skipped. The difference is one word in the statement and a completely different recurrence, and confusing them is the most common error here.
For subsequences, a mismatch allows dropping one character from either string and continuing. For substrings a mismatch ENDS the run, because contiguity cannot be repaired:
a[i] == b[j] -> dp[i][j] = dp[i-1][j-1] + 1
otherwise -> dp[i][j] = 0
The other consequence of that zero is that the answer is not dp[n][m]. Each
entry is the length of the run ENDING at that pair, so the answer is the largest
entry anywhere in the table. Reading the bottom-right corner returns the run that
happens to end at the last characters, which is usually 0.
Both differences follow from one observation: a substring must be unbroken, so there is nothing to carry across a mismatch.
Constraints - `1 ≤ length of each string ≤ 1000` - Both are lowercase English letters.
Input
Two lines containing the strings a and b.
Output
Print the length of the longest contiguous run appearing in both, or 0 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.