Hi,

I'm looking for a problem of finding the length of the k-th longest common subsequences. Requiring the subsequences being increasing naturally leads to the k-th longest increasing "common" subseq problem, but what if we only require them being "common"? The limiting law of the length of the k-th longest increasing subsequences has been studied a lot (arbitrary distribution, nonasymptotically, the sequences/words are assumed to be generated from a distribution). But for the "common" setting, only k=1 is discussed and I didn't find an analog even limited to uniformly distributed binary words. (Finding the length of the increasing subseq of a binary string looks quite weird, but some people worked on it anyway...)

I asked some math people working in this field, but they never saw papers like this. I am wondering if there is any OJ problem (since research and programming contests sometimes have gaps...) Did anyone see one that requires a "k-th" and "common" subsequence? Thanks!!