Improved bounds on the average length of longest common subsequences

DOI10.1145/1516512.1516519zbMath1325.68308OpenAlexW2091419774WikidataQ56171968 ScholiaQ56171968MaRDI QIDQ3452214

George S. Lueker

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1516512.1516519

zbMATH Keywords

dynamic programmingaverage-case analysislongest common subsequencesArratia-Steele conjecture

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15) Permutations, words, matrices (05A05) Combinatorial probability (60C05) Algorithms on strings (68W32)

Related Items (6)

Periodic words, common subsequences and frogs ⋮ Lower bounds for moments of global scores of pairwise Markov chains ⋮ Sparse long blocks and the micro-structure of the longuest common subsequences ⋮ Quasi-random words and limits of word sequences ⋮ Length of the Longest Common Subsequence between Overlapping Words ⋮ A Formula for the Mean Length of the Longest Common Subsequence

This page was built for publication: Improved bounds on the average length of longest common subsequences