Longest Common Substring
mediumStrings II+20 XPTime limit 3s
Two students' essays are compared for copying. Find the length of the longest piece of text that appears in both, as a contiguous block (a substring — not a subsequence). For codingninja and ninjacoder the answer is 5 (ninja). If they share no character, the answer is 0.
Input:
- line 1: string
a - line 2: string
b
Both contain only lowercase letters.
Output: the length of the longest common substring.
Constraints: 1 ≤ length of each ≤ 1000.
Think about it: let dp[i][j] be the length of the longest common block ending exactly at a[i] and b[j]. It is dp[i−1][j−1] + 1 when the characters match, and 0 otherwise. The answer is the largest value in the table. Only the previous row is needed.
Sample input 1
codingninja ninjacoder
Sample output 1
5
Sample input 2
abc xyz
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).