High precision simulations of the longest common subsequence problem

Abstract

The longest common subsequence problem is a long studied prototype of pattern matching problems. In spite of the effort dedicated to it, the numerical value of its central quantity, the Chvatal-Sankoff constant, is not yet known. Numerical estimations of this constant are very difficult due to finite size effects. We propose a numerical method to estimate the Chvatal-Sankoff constant which combines the advantages of an analytically known functional form of the finite size effects with an efficient multi-spin coding scheme. This method yields very high precision estimates of the Chvatal-Sankoff constant. Our results correct earlier estimates for small alphabet size while they are consistent with (albeit more precise than) earlier results for larger alphabet size.

8 pages, 4 figures

Cited by in corpus (6)

• $LCSk$++: Practical similarity metric for long strings
• Sparse long blocks and the variance of the longest common subsequences in random words
• Unzipping of two random heteropolymers: Ground state energy and finite size effects
• Simulations, Computations, and Statistics for Longest Common Subsequences
• Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences
• Longest common subsequences between words of very unequal length