#P18418. LCSLCSLCS
LCSLCSLCS
LCSLCSLCS
给定两个非空字符串 ,它们都由大写英文字母组成,且 。另外给定两个整数 ,满足 。
记 为将 份字符串 依次连接得到的字符串, 的含义类似。求 与 的最长公共子序列的长度。
子序列允许删除字符,保留下来的字符须保持原有相对顺序,不要求连续。
输入格式
第一行包含两个整数 ,满足 。
第二行包含一个非空字符串 ,第三行包含一个非空字符串 。两串长度均不超过 ,且仅包含大写英文字母 A 到 Z。
输出格式
输出一个整数,表示 与 的最长公共子序列的长度。
样例 1
输入:
10 10
AB
BA
输出:
19
样例 2
输入:
100000000 100000000
A
AB
输出:
100000000