CMPSSTR - Compare Substring

* This problem is of authorship and property of TopCoder (www.topcoder.com/tc) and adapted by Alessandro B. for authorized use in URI OJ.
* Unauthorized reproduction of this problem statement without the prior written consent of TopCoder, Inc. is strictly prohibited.

Find the longest common substring between the two informed Strings. The substring can be any part of the String, including the entire String. If there is no common substring, return 0. The search is case sensitive ('x' != 'X').

Input

The input contains several test cases. Each test case is composed by two lines that contains a string each. Both input Strings will contain between 1 and 50, inclusive, letters (a-z, A-Z), and/or spaces.

Output

The length of the longest common substring between the two Strings.

Example

Input:
abcdef
cdofhij
TWO
FOUR
abracadabra
open
Hey This java is hot
Java is a new paradigm Output: 2
1
0
7

Added by:noname
Date:2015-09-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:TopCoder* USA

hide comments
2021-10-12 04:41:53
Suffix Automaton seems works in this problem...
2016-07-12 16:46:35 Piyush Kumar
@shikhar jinal : no, Input till EOF
2015-10-17 00:02:40 shikhar jindal
we have to input number of test cases or not??
2015-09-25 20:21:24
:| Time limit exceeded rey!
2015-09-25 14:36:32 Vipul Srivastava
O(n*m) worked for me in C++. n and m being the string lengths.

Last edit: 2015-09-25 14:37:33
2015-09-24 19:09:22 eightnoteight
how many test cases will be given? what is the required complexity range?
2015-09-21 11:15:32 Scape
Why is this not in tutorial?
2015-09-20 14:03:13 Vipul Srivastava
@ritesh: U have to find the longest common substring. Substring is contiguous occurence of letters in both the strings. U are confusing substring with subsequence.
2015-09-20 01:03:21
shouldn't the first output be 3 as there are three common elements viz. c,d,f ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.