解题思路

• 两个孩子各认识一个字符串：小明的字符串 s、小红的字符串 t。若先说 x 再说 y，小红的得分是满足“x 的后缀 = y 的前缀”的最大长度 k。

• 题目等价为：分别计算

  1. k1 = LPSuffixPrefix(s, t)（t 的最长前缀也是 s 的后缀）
  2. k2 = LPSuffixPrefix(t, s)（s 的最长前缀也是 t 的后缀） 输出 min(k1, k2)。

• 相关算法：使用 KMP 的前缀函数 或 Z-Algorithm 均可在线性时间求解“字符串 A 的后缀与字符串 B 的前缀的最大重合”。这里采用 KMP 前缀函数：

题目内容

有两个小朋友玩词语接龙游戏，他们只认识两个字符串。若小明先说出长度为 $n$ 的字符串 $s$ ，小红只能说长度为 $m$ 的字符串 $t$ (相反的，若小明先说出 $t$，小红只能说 $s$ )。

游戏中定义小红的得分为 $k$ 。其中 $k$ 是最大的满足“小明所说字符串的后 $k$ 位” 和 “小红所说字符串的前 $k$ 位” 是-样的这一前提的数字。例如小明说 $s$ 、小红说 $t$ 时,小红的得分即为 $s[n-k+1]$ ~ $s [n]==t [1]$ ~ $t [k]$ 。

小明想知道他应该说哪个字符串，才能让小红的得分最少，请你输出最少的得分即可。

输入描述

两行，每行一个仅包含小写字母的字符串，代表小明和小红当前认识的两个字符串。

$1≤$ 字符串长度 $≤1000$

输出描述

输出小红可能获得的最少得分。

样例1

输入

ababab
babaa

输出

1

说明

如果小明说 $ababab$，小红说 $babaa$，最大满足 $k=3$ (即 $bab$)

如果小明说 $babaa$，小红说 $ababab$，最大满足 $k=1$ (即 $a$ )

最终答案为 $1$