alan的字符串

题号：NC219235
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小y有两个字符串 $a$ , $b$
$n$ 和 $m$ 分别为 $a$ 和 $b$ 的长度
小y想选一个 $a$ 和 $b$ 的公共子序列，然后她希望这个子序列是回文的
并且希望这个公共子序列尽可能长
可是小y不会，于是就请教了alan
alan瞬间就秒掉了，你知道alan是怎么做的吗？orz

第一行包含一个字符串，表示字符串  。 第二行包含一个字符串，表示字符串  。

一行，包含一个整数，表示满足条件  和  的最长子序列的长度

示例1

复制

aaaaa
bbbbb

复制

示例2

复制

aaaaa
abbbb

复制

数据范围：      
字符串a和b内只包含小写字母