Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.