|
This article is cited in 1 scientific paper (total in 1 paper)
A formula for the mean length of the longest common subsequence
Sergej V. Znamenskij Ailamazyan Program Systems Institute of RAS, Peter the First, 4, Veskovo village, Pereslavl area, Yaroslavl region, 152021,
Russia
Abstract:
The expected value $E$ of the longest common subsequence of letters in two random words is considered as a function of the $\alpha=|A|$ of alphabet and of words lengths $m$ and $n$. It is assumed that each letter independently appears at any position with equal probability. A simple expression for $E(\alpha, m, n)$ and its empirical proof are presented for fixed $ \alpha $ and $ m + n $. High accuracy of the formula in a wide range of values is confirmed by numerical simulations.
Keywords:
longest common subsequence, expected value, LCS length, simulation, asymptotic formula.
Received: 10.10.2016 Received in revised form: 10.11.2016 Accepted: 20.12.2016
Citation:
Sergej V. Znamenskij, “A formula for the mean length of the longest common subsequence”, J. Sib. Fed. Univ. Math. Phys., 10:1 (2017), 71–74
Linking options:
https://www.mathnet.ru/eng/jsfu526 https://www.mathnet.ru/eng/jsfu/v10/i1/p71
|
Statistics & downloads: |
Abstract page: | 199 | Full-text PDF : | 83 | References: | 31 |
|