Problem B: 最长公共递增子序列
Memory Limit:128 MB
Time Limit:1.100 S
Judge Style:Text Compare
Creator:
Submit:36
Solved:4
Description
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共递增子序列的长度。如果不存在公共递增子序列 ,返回 0 。
字符串的子序列是指由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
字符串的递增子序列是指,字符串的子序列按ASCII码顺序递增。例如,"ace" 是 "abcfde" 的递增子序列,但 "afe" 不是 "abcfde" 的递增子序列。
两字符串具有相同递增子序列为公共递增子序列。例如,”abcd“是字符串”abcfde“与字符串”abcfdfe“公共子序列,但是其最长公共子序列为”abcde“。
Input
输入共两行,分别为两个字符串 text1 和 text2。
Output
返回这两个字符串的最长公共递增子序列的长度。如果不存在公共递增子序列 ,返回 0。
Sample Input Copy
abcfde
abcfdfe
Sample Output Copy
5
HINT
【提示1】 1 <= text1.length, text2.length < 2^16
【提示2】 text1 和 text2 仅由小写英文字符组成。