A subsequence of a string s is a string that can be obtained by erasing zero or more characters from s. For example, "aacb", "c", "", and "abacaba" are subsequences of "abacaba", but "bbc" is not.
Common subsequences of strings s1 and s2 are strings that are subsequences of both s1 and s2.
A string s1 is called a cyclic shift of string s if s1 can be obtained by removing zero or more characters from the beginning of string s and appending them to the end of string s in the same order. For example, strings "abcde", "bcdea" and "eabcd" are cyclic shifts of string "abcde", but "cdeba" is not.
You are given two String[]s a and b.
Construct a string A by concatenating all the elements of a, and construct a string B by concatening all the elements of b.
Consider all common subsequences for all pairs (x, y), where x is any cyclic shift of string A, and y is any cyclic shift of string B. There are length(A) * length(B) such pairs. Find the common subsequence among all of these that comes last alphabetically, and return the last
suffixLength characters of that subsequence. If the subsequence contains less than suffixLength characters, then return the whole subsequence.
|