Expected length of the longest common subsequence of multiple strings

Authors

  • Ray Li Santa Clara University
  • William Ren Santa Clara University
  • Yiran Wen Santa Clara University

Keywords:

Longest Common Subsequence, Chvatal-Sankoff constant, Expected Value, Multiple Strings, Greedy Algorithm

Abstract

http://dx.doi.org/10.1017/S0004972712000330

Published

2026-08-01

Issue

Vol. 114 No. 1 (2026)

Section

Articles
In these notes, the Australian Mathematical Publishing Association Incorporated, Cambridge Journals Online, Cambridge University Press, and the Bulletin are abbreviated to AMPAI, CJO, CUP, and the Bulletin.

Copyright is held by AMPAI. Under the standard arrangement, the article will be made freely accessible to the public five (5) years after publication. Alternatively, for an initial fee of $USD600, immediate open access under a creative commons license will be provided on the CUP online platform.

  1. The Bulletin's policy is to acquire copyright for as many articles as possible, for two reasons:
    1. ownership of copyright by one central organisation tends to ensure maximum international protection against unauthorised use;
    2. it also ensures that requests by third parties to reprint or reproduce a contribution, or part of it, are handled efficiently and in accordance with a general policy that is sensitive both to any relevant changes in international copyright legislation and to the general desirability of encouraging the dissemination of knowledge.
  2. Copyright acts in various countries confer 'moral rights' on authors. In some cases, an author's 'right of paternity', that is the right to be properly credited whenever the work is published (or performed or broadcast), must be asserted in writing.
  3. Notwithstanding the assignment of copyright in their contribution, all authors retain the following non-transferable rights:
    1. The right to post the abstract and a link to the online edition of the Bulletin at CJO or at the Bulletin website.
    2. The right to post the definitive version of the contribution as published at CJO (in PDF or HTML) in the Institutional Repository of the institution in which they worked at the time the paper was first submitted, no sooner than two years after first publication of the paper in the journal, subject to file availability and provided the posting includes a prominent statement of the full bibliographical details, a copyright notice in the name of the copyright holder (AMPAI or another body, as appropriate), and a link to the online edition of the Bulletin at CJO. Inclusion of this definitive version after two years in Institutional Repositories outside of the institution in which the author worked at the time the paper was first submitted will be subject to the additional permission of CUP on behalf of AMPAI (not to be unreasonably withheld).
    3. The right to make hard copies of the article or an adapted version for their own purposes, including the right to make multiple copies for course use by their students, provided no sale is involved.
    4. The right to reproduce the paper or an adapted version of it in any volume of which they are an editor or an author, but otherwise permission must be sought from CUP. Permission will automatically be given to the publisher of such a volume, subject to normal acknowledgement.
  4. CUP (on behalf of AMPAI) will use its best endeavours to ensure that any direct request received to reproduce a contribution, or a substantial part of it, in another publication (which may be an electronic publication) is approved by the contributor before permission is given. Multiple authors should nominate one author only to respond to such requests.
  5. CUP co-operates in various licensing schemes that allow material to be photocopied within agreed restraints (e.g., the CCC in the USA and the CLA in the UK). Any proceeds received from such licenses, together with any proceeds from sales of subsidiary rights in the Bulletin, directly support its continuing publication.
  6. It is understood that in some cases copyright will be held by the contributor's employer. If so, CUP (on behalf of AMPAI) requires exclusive permission to deal with requests from third parties, on the understanding that any requests received from third parties will be handled in accordance with paragraphs 4 and 5 above (note that approval will be sought for the proposed use from the contributor, not the employer).
  7. If a contribution includes textual or illustrative material not in your copyright and not covered by fair use/fair dealing, permission must be obtained from the relevant copyright owner (usually the publisher or via the publisher) for the nonexclusive right to reproduce the material worldwide in all forms and media, including electronic publication. The relevant permission correspondence must be attached to this form. If in doubt about whether or not permission is required, please consult: the Permissions Controller, Cambridge University Press, The Edinburgh Building, Shaftesbury Road, Cambridge CB2 2RU, UK. Fax: +44 (0)1223 315052. Email: lnicol@cambridge.org.
  8. The information provided on this form will be held in perpetuity by AMPAI for record purposes. The name(s) and address(es) of the author(s) of the contribution may be reproduced in the Bulletin and provided to print and online indexing and abstracting services and bibliographic databases