← 返回题目列表

Codeforces · 427/D

D. 比赛与接球

中文机器翻译题面 查看原题

警察总部正在监控不同频率级别的信号。他们从两个不同频率获得了两个可疑编码字符串 s1 和 s2 作为信号。他们怀疑这两根绳子来自两个不同的犯罪分子,他们正计划做一些邪恶的事情。

现在他们正在尝试在这两个字符串之间找到最小长度的公共子字符串。子字符串在第一个字符串中只能出现一次,并且在第二个字符串中也只能出现一次。

给定两个由小写拉丁字母组成的字符串 s1 和 s2,找到 s1 和 s2 中最小(按长度)的公共子串 p,其中 p 是 s1 和 s2 中的唯一子串。有关子字符串和唯一性的正式定义,请参阅注释。

输入

输入的第一行包含 s1,第二行包含 s2 (1 ≤ |s1|, |s2| ≤ 5000)。两个字符串均由小写拉丁字母组成。

输出

打印 s1 和 s2 的最小公共唯一子串的长度。如果 s1 和 s2 没有共同的唯一子串,则打印 -1。

示例

输入 #1

apple
pepperoni

输出 #1

2

输入 #2

lover
driver

输出 #2

1

输入 #3

bidhan
roy

输出 #3

-1

输入#4

testsetses
teeptes

输出#4

3

注意

假设我们有字符串 a = a1a2a3...a|a|,其中 |a|是字符串a的长度,ai是字符串的第i个字母。

我们将字符串 alal + 1al + 2...ar (1 ≤ l ≤ r ≤ |a|) 称为字符串 a 的子串 [l, r]。

子串 [l, r] 在 a 中是唯一的当且仅当不存在 l1, r1 对使得 l1 ≠ l 并且子串 [l1, r1] 等于 a 中的子串 [l, r] 时。