Siberian Federal University 
- Issue
- Journal of Siberian Federal University. Mathematics & Physics. 2017 10 (1)
- Authors
- Znamenskij, Sergej V.
- Contact information
- Znamenskij, Sergej V.: Ailamazyan Program Systems Institute of RAS Peter the First, 4, Veskovo village, Pereslavl area, Yaroslavl region, 152021 Russia;
- Keywords
- longest common subsequence; expected value; LCS length; simulation; asymptotic formula
- Abstract
The expected value E of the longest common subsequence of letters in two random words is considered as a function of the = jAj 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( ; m; n) and its empirical proof are presented for fixed and m + n. High accuracy of the formula in a wide range of values is confirmed by numerical simulations
- Pages
- 71–74
- Paper at repository of SibFU
- https://elib.sfu-kras.ru/handle/2311/30296
Journal of Siberian Federal University. Mathematics & Physics / A Formula for the Mean Length of the Longest Common Subsequence
Full text (.pdf)