环形日志匹配

题目描述

给定两个字符串 $A$ 与 $B$（仅包含小写字母）。你可以将 $A$ 进行一次循环位移（即把某个前缀挪到末尾），得到 $A'$。

请你求出：在所有可能的循环位移中，$A'$ 与 $B$ 的最长公共子序列长度的最大值。

输入格式

输入共两行。

• 第一行是字符串 $A$。
• 第二行是字符串 $B$。

输出格式

输出一行，一个整数，表示最大可能的最长公共子序列长度。

输入输出样例 #1

输入 #1

abac
cab

输出 #1

3

样例解释 #1

将 $A$ 循环位移为 acab 时，acab 与 cab 的最长公共子序列长度为 $3$。

数据范围

对于所有测试数据，保证：

• $1 \le |A|,|B| \le 200$。