MSTRING - String problem


Substring of some string A is defined as one or more (not necessary succeeding) elements of the string with maintaining the sequence.

There are given two strings, string VOKI and string TOKI. Write the program that will calculate the length of any shortest substring of string VOKI such as it is not substring of string TOKI.

Input

In first line of input file there is string VOKI and in second one is string TOKI. The only characters that will occur are lowercase characters of English alphabet (‘a’- ‘z’). String lengths will be less or equal to 1000.

Note: input data will be such so there will always be a solution.

Output

In the first line of file you should print the length of wanted substring.

Sample

Sample input
 
banana 
anbnaanbaan 
 
Sample output
 
5 
 
(eg. banna) 

Sample input
 
babab 
babba 
 
Sample output
 
3 
 
(eg. aab) 

hide comments
Mukesh Yadav: 2013-01-29 19:31:33

Had A Bad Time , lcs was easy : P

SAHIL SAREEN: 2013-01-07 17:39:47

Sample is not clear..
"banna" isnt a substring of either of the strings..
and "aab" isnt a part of VOKI(the first string) as the problem states..

Last edit: 2013-01-07 17:40:24
BB: 2010-11-29 15:12:31

very funny! 'a' -> 'z' means nothing.
you can't ac with that condiction!

Brian Bi: 2010-11-14 09:23:31

I still think the author should use the term "subsequence", not because the problem statement is confusing as is, but because, for consistency, the same term should have the same meaning throughout a given field of study.

~!(*(@*!@^&: 2009-04-20 16:16:57

they define the definition of substring very clearly in the beginning of the problem.

[Trichromatic] XilinX: 2009-04-20 16:16:57

In this problem, "substring" actually means subsequence.

JiaZhiHao: 2009-04-20 16:16:57

In Case 2,why 'aab' is a substring of 'babab'


Added by:~!(*(@*!@^&
Date:2009-02-28
Time limit:0.233s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 04