Length of the longest common subsequence between overlapping words

2018/03/08 by Bukh, Boris, Hogenson, Raymond · 2 citations
#05A05 #60C05 #68R15 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1803.03238

Abstract

Given two random finite sequences from [k]ⁿ such that a prefix of the first sequence is a suffix of the second, we examine the length of their longest common subsequence. If ℓ is the length of the overlap, we prove that the expected length of an LCS is approximately max(ℓ, 𝔼[L_n]), where L_n is the length of an LCS between two independent random sequences. We also obtain tail bounds on this quantity.

Cited by

• Asymptotically half of binary words are shuffle squares
• Incorporating indel channels into average-case analysis of seed-chain-extend

Related

• Longest common subsequences between words of very unequal length
• Simulations, Computations, and Statistics for Longest Common Subsequences
• Repetition-free longest common subsequence of random sequences
• Expected Length of the Longest Common Subsequence of Multiple Strings
• Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences