Match & Catch

1000ms

524288K

Description:

Police headquarter is monitoring signal on different frequency levels. They have got two suspiciously encoded strings s₁ and s₂ from two different frequencies as signals. They are suspecting that these two strings are from two different criminals and they are planning to do some evil task.

Now they are trying to find a common substring of minimum length between these two strings. The substring must occur only once in the first string, and also it must occur only once in the second string.

Given two strings s₁ and s₂ consist of lowercase Latin letters, find the smallest (by length) common substring p of both s₁ and s₂, where p is a unique substring in s₁ and also in s₂. See notes for formal definition of substring and uniqueness.

Input:

The first line of input contains s₁ and the second line contains s₂ (1 ≤ |s₁|, |s₂| ≤ 5000). Both strings consist of lowercase Latin letters.

Output:

Print the length of the smallest common unique substring of s₁ and s₂. If there are no common unique substrings of s₁ and s₂ print -1.

Sample Input:

apple
pepperoni

Sample Output:

Sample Input:

lover
driver

Sample Output:

Sample Input:

bidhan
roy

Sample Output:

-1

Sample Input:

testsetses
teeptes

Sample Output:

Note:

Imagine we have string a = a₁a₂a₃...a_|a|, where |a| is the length of string a, and a_i is the i^th letter of the string.

We will call string a_la_l + 1a_l + 2...a_r (1 ≤ l ≤ r ≤ |a|) the substring [l, r] of the string a.

The substring [l, r] is unique in a if and only if there is no pair l₁, r₁ such that l₁ ≠ l and the substring [l₁, r₁] is equal to the substring [l, r] in a.

Informação

Provedor Codeforces

Código CF427D