Geodesic
A formula for the mean length of the longest common subsequence
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 10 (2017) no. 1, pp. 71-74

Voir la notice de l'article provenant de la source Math-Net.Ru

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, asymptotic formula.
Mots-clés : simulation 
@article{JSFU_2017_10_1_a10,
     author = {Sergej V. Znamenskij},
     title = {A formula for the mean length of the longest common subsequence},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {71--74},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/}
}
TY  - JOUR
AU  - Sergej V. Znamenskij
TI  - A formula for the mean length of the longest common subsequence
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2017
SP  - 71
EP  - 74
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/
LA  - en
ID  - JSFU_2017_10_1_a10
ER  - 
%0 Journal Article
%A Sergej V. Znamenskij
%T A formula for the mean length of the longest common subsequence
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2017
%P 71-74
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/
%G en
%F JSFU_2017_10_1_a10
Sergej V. Znamenskij. A formula for the mean length of the longest common subsequence. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 10 (2017) no. 1, pp. 71-74. http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/