2001/06/17 by R. Bundschuh, Ralf Bundschuh · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Algorithms and Data Compression #cond-mat.stat-mech #q-bio.QM
paper · pdf · doi:10.1007/s100510170102
8 pages, 4 figures
arxiv created 2001/06/17 · openalex publication_date 2001/08/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.