题目内容

现有两个字符串 text1 与 text2。对于某个字符串，若删除其中零个或多个字符后，剩余字符仍保持原本的先后顺序，则得到的新字符串称为它的一个子序列。如果某个字符串同时是 text1 和 text2 的子序列，就称它为二者的公共子序列。

请你在 text1 与 text2 的所有公共子序列中，找出最长的那个，并返回它包含的字符数量。如果二者不存在任何公共子序列，则返回 0。

约束条件：两个字符串的长度都在 1 到 1000 之间；两个字符串都只由小写英文字母组成。

输入描述

输入包含两个参数：

• 一个字符串 text1，表示第一个待比较的字符串；
• 一个字符串 text2，表示第二个待比较的字符串。

输出描述

返回一个整数，表示 text1 和 text2 的最长公共子序列长度；如果二者不存在任何公共子序列，则返回 0。

样例1

输入

a
a

输出

1

说明

两个字符串都是单个字符 a，且完全相同。text1 的子序列可以是空串或 a，text2 的子序列也可以是空串或 a。它们的最长公共子序列就是 a，因此长度为 1。

样例2

输入

a
b

输出

0

说明

text1 只包含字符 a，text2 只包含字符 b。两个字符串没有任何相同字符，因此无法形成任何非空公共子序列。所以最长公共子序列长度为 0。

样例3

输入

abcbdab
bdcaba

输出

4

说明

一个公共子序列是 bcba。在 text1 = abcbdab 中，可以依次取第 2 个字符 b、第 3 个字符 c、第 4 个字符 b、第 6 个字符 a；在 text2 = bdcaba 中，可以依次取第 1 个字符 b、第 3 个字符 c、第 5 个字符 b、第 6 个字符 a。

这说明两个字符串存在长度为 4 的公共子序列。同时，任意长度为 5 的候选子序列都无法在两个字符串中按顺序完整匹配，因此最长公共子序列长度为 4。

样例4

输入

abac
cab

输出

2

说明

一个公共子序列是 ab。在 text1 = abac 中，可以依次取第 1 个字符 a 和第 2 个字符 b；在 text2 = cab 中，可以依次取第 2 个字符 a 和第 3 个字符 b。

这两个字符串可以找到长度为 2 的公共子序列，但无法找到长度为 3 的公共子序列，因此结果为 2。