https://doi.org/10.1007/s100510170102
High precision simulations of the longest common subsequence problem
Department of Physics, University of California at San Diego,
La Jolla, CA 92093-0319, USA
Corresponding author: a rbund@mps.ohio-state.edu
Received:
12
April
2001
Published online: 15 August 2001
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 Chvátal-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 Chvátal-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 Chvátal-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.
PACS: 05.45.-a – Nonlinear dynamics and nonlinear dynamical systems / 02.60.Pn – Numerical optimization / 89.75.Kd – Patterns / 02.50.Ey – Stochastic processes
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2001
