RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



J. Sib. Fed. Univ. Math. Phys.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


J. Sib. Fed. Univ. Math. Phys., 2017, Volume 10, Issue 1, Pages 71–74 (Mi jsfu526)  

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.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation RFMEFI60414X0138
This work was performed under financial support from the Government, represented by the Ministry of Education and Science of the Russian Federation (Project ID RFMEFI60414X0138).


DOI: https://doi.org/10.17516/1997-1397-2017-10-1-71-74

Full text: PDF file (121 kB)
References: PDF file   HTML file

Bibliographic databases:

Document Type: Article
UDC: 004.412
Received: 10.10.2016
Received in revised form: 10.11.2016
Accepted: 20.12.2016
Language: English

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

Citation in format AMSBIB
\Bibitem{Zna17}
\by Sergej~V.~Znamenskij
\paper A formula for the mean length of the longest common subsequence
\jour J. Sib. Fed. Univ. Math. Phys.
\yr 2017
\vol 10
\issue 1
\pages 71--74
\mathnet{http://mi.mathnet.ru/jsfu526}
\crossref{https://doi.org/10.17516/1997-1397-2017-10-1-71-74}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000412012600011}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85011883141}


Linking options:
  • http://mi.mathnet.ru/eng/jsfu526
  • http://mi.mathnet.ru/eng/jsfu/v10/i1/p71

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. S. V. Znamenskii, “Priblizhenie dliny naibolshei obschei podposledovatelnosti pary sluchainykh strok”, Programmnye sistemy: teoriya i prilozheniya, 7:4 (2016), 347–358  mathnet
  • Журнал Сибирского федерального университета. Серия "Математика и физика"
    Number of views:
    This page:77
    Full text:35
    References:15

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019