LCS Again! <Bizongo>

0

0 votes
Binary search algorithm, String, Hard, Algorithms, Hash function, Hashing algorithm
Problem

Ash is a professor of Data Structures and Algorithms in a very famous college of Kanto region. He taught his students the concept of Longest Common Subsequence today. He is planning to take quiz tomorrow. He wants to create one question for the same. He believes that the students should gain something from the quiz. As he taught concept of Longest Common Subsequence today, he creates a question somewhat similar to that. The question is as follows:

  • Given two strings s and t consisting of only lowercase English alphabets, find the Longest Common Substring of the two strings. 

He feels like this question will be very tough for his students. So, he asks you to solve it first. Can you crack it?

Input:
The first line contains a string s of length n.
The second line contains a string t of length m.

Output:
Output a single line denoting the length of Longest Common Substring of the two strings.

Constraints:

1n,m105

It is guaranteed that the strings s and t only contains lowercase English alphabets.
 

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

The longest common substring is "ab". Other common substrings are "a", "c" and "b".

Editor Image

?