Bobo has two strings s and t. He would like to choose two subsequences x from s and y from t such that: + x is lexicographically smaller than or equal to y. + The sum of |x| and |y| is maximal, where |s| denotes the length of the string s. Note that: + Both x and y could be empty string. + A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. + String x is lexicographically less than string y, if either x is a prefix of y , or there exists such i , that xi
Bobo has two strings s and t. He would like to choose two subsequences x from s and y from t such that: + x is lexicographically smaller than or equal to y. + The sum of |x| and |y| is maximal, where |s| denotes the length of the string s. Note that: + Both x and y could be empty string. + A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. + String x is lexicographically less than string y, if either x is a prefix of y (and x ≠ yx ne yx = y), or there exists such i (1 ≤ i ≤ min(∣x∣, ∣y∣)1 le i le min(|x|, |y|)1 ≤ i ≤ min(∣x∣, ∣y∣)), that xi < yix_i < y_ixi < yi, and for any j (1 ≤ j < i1 le j < i1 ≤ j < i) xj = yjx_j = y_jxj = yj.
