Longest Common Substring

Interview

Time limit2sMemory limit256 MB

Summary

Given two uppercase strings of length up to 4000, find the length of the longest substring that occurs contiguously in both.

Level: Medium5 of 10
Topics: Dynamic programming, String, Sliding window, Binary search
Solved: No attempts yet

Problem

Given two strings, write a program that finds the length of the longest substring that appears contiguously in both of them.

A substring $t$ of a string $s$ is a run of characters that occurs contiguously inside $s$ . For example, substrings of the string ABRACADABRA include ABRA, RAC, D, ACADABRA, ABRACADABRA, and the empty string. On the other hand, ABRC, RAA, BA, and K are not substrings.

Common substrings of the two strings ABRACADABRA and ECADADABRBCRDARA include CA, CADA, ADABR, and the empty string. Among these the longest common substring is ADABR, whose length is 5. If the two strings are UPWJCIRUCAXIIRGL and SBQNYBSBZDFNEV, the only common substring is the empty string, so the answer is 0.

Input

The first and second lines each contain one string. Both strings consist only of uppercase letters, and each has length between 1 and 4000, inclusive.

Output

Print, on the first line, the length of the longest substring contained in both strings. If the only common substring is the empty string, print 0.

Examples2

Example 1
Input
```
ABRACADABRA
ECADADABRBCRDARA
```
Expected output
```
5
```
Example 2
Input
```
UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV
```
Expected output
```
0
```