当 Mahmoud 和 Ehab 练习 IOI 时,他们发现了一个问题,名称为 Longest common subsequence。他们解决了这个问题,然后埃哈卜向马哈茂德提出了另一个问题。
给定两个字符串 a 和 b,求它们的最长不常见子序列的长度,该子序列是其中一个字符串的子序列而不是另一个字符串的子序列的最长字符串。
某个字符串的子序列是字符串中以相同顺序出现的字符序列,出现的次数不必是连续的,例如,字符串“ac”、“bc”、“abc”和“a”是字符串“abc”的子序列,而字符串“abbc”和“acb”则不是。空字符串是任何字符串的子序列。任何字符串都是其自身的子序列。
输入
第一行包含字符串 a,第二行包含字符串 b。这两个字符串都非空,并且由英文字母的小写字母组成。每个字符串的长度不超过105个字符。
输出
如果没有不常见的子序列,则打印“-1”。否则打印 a 和 b 的最长非公共子序列的长度。
示例
输入 #1
abcd defgh
输出 #1
5
输入 #2
a a
输出 #2
-1
注意
在第一个示例中:您可以从字符串 b 中选择“defgh”,因为它是字符串 b 中不作为字符串 a 的子序列出现的最长子序列。