{'fraction_non_alphanumeric': 0.03909440307470574, 'fraction_numerical': 0.016574585635359115, 'mean_word_length': 4.234988997170701, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
High precision simulations of the longest common subsequence problem

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.


Introduction
Pattern matching problems have been of central interest in such different areas of science as image processing, speech recognition, time series analysis, and biological sequence comparison for a large number of years. In many practical applications of pattern matching, it is important to be able to characterize the amount and/or strength of patterns found in random data in order to be able to distinguish meaningful patterns from random ones [1]. This requires a quantitative theory of pattern matching procedures which does not only characterize universal characteristics like scaling laws but which also provides specific numerical values for non-universal quantities.
One of the simplest pattern matching problems is the longest common subsequence (LCS) problem. It is a special case of the sequence comparison problem, which is a very important tool in modern molecular biology [2]. As a prototype for pattern matching it has enjoyed the attention of mathematicians and computer scientists for a long time [3,4,5,6,7,8,9,10,11,12,13]. One of the central quantities in the LCS problem is the average fraction of matches in the longest common subsequence of two very long random strings also known as the Chvátal-Sankoff constant a c [3]. However, in spite of the relative simplicity of the LCS problem and the long time it has been studied, the numerical value of the Chvátal-Sankoff constant is still unknown. There has been a long standing conjecture by Arratia [14] for its value based on numerical simulations where c is the size of the alphabet from which the sequences are chosen at random. This conjecture has been recently shown to hold for a first-passage percolation version of the LCS problem using the analogy [15] to surface growth as described by the Kardar-Parisi-Zhang (KPZ [17]) equation [16] and a cavity method [12,13]. In the language of surface growth the Chvátal-Sankoff constant takes the interpretation of the average growth velocity of the surface or of the ensemble averaged free energy per length in the directed polymer picture which is equivalent to the KPZ equation.
For the original Chvátal-Sankoff constant (i.e., not the first-passage percolation version) a variety of upper and lower bounds have been rigorously proven in the mathematical literature [3,4,7,8,10,11] which are all consistent with Arratia's conjecture. Short of a rigorous result for the value of the Chvátal-Sankoff constant, extensive numerical studies are the only way to shed some light on the validity of Arratia's conjecture. The difficulty with numerical studies is that the Chvátal-Sankoff constant is defined as an asymptotic quantity in the limit that the sequences the longest common subsequence of which is computed are infinite. Simulations at finite sequence length always observe finite size effects the size and even functional form of which is not known. In fact, two recent numerical studies [11,12,13] assume different functional forms of the finite size effect. Thus, they come to different conclusions about the value of the Chvátal-Sankoff constant although both studies agree on the fact that the Chvátal-Sankoff constant differs from its conjectured value Eq. (1).
In this communication, we will remedy this dilemma in two different ways. First, we will use a slightly different geometry in which we perform our simulations. The advantage of this geometry is that the form of the finite size behavior is theoretically known from the analogy to surface growth [15] and does not have to be inferred from the numerical data. We will prove this finite size behavior for the first-passage percolation case explicitly. While this result reproduces the known value of the first-passage percolation version of the Chvátal-Sankoff constant, it additionally provides the complete finite-size correction in terms of Legendre polynomials and an explicit formula for the prefactor of the leading finite size correction term. We will use this to validate our numerical procedure. Additionally, we will reformulate the LCS problem in a way that allows for a multi-spin coding scheme, in which 64 lattice sites are updated in parallel by simple bitwise logical operations. This extremely efficient code allows us to average over a large number of systems with several million letters each. This yields the value of the Chvátal-Sankoff constant with a precision of one part in 10 6 .

Longest Common Subsequence problem
The LCS problem is defined as follows: Given two sequences x = x 1 . . . x N and y = y 1 . . . y N of letters x i and y j independently chosen with equal probabilities from an alphabet of size c, find their longest common subsequence. A common subsequence of length ℓ is given by a set of (i k , j k )'s with 1 ≤ i 1 < . . . < i ℓ ≤ N and 1 ≤ j 1 < . . . < j ℓ ≤ N such that x i k = y j k for all k ∈ {1, . . . , ℓ}. We denote the length of the longest common subsequence of two given sequences by L(N ). It is a random variable since it depends on the specific choice of the sequences. Its expectation value averaged over the ensemble of all sequence pairs is L(N ) . Chvátal and Sankoff noted [3] that this expectation value is asymptotically proportional to the length of the sequences, i.e., L(N ) ≈ a c N . The prefactor a c is now called the Chvátal-Sankoff constant and depends only on the size c of the alphabet. To find high precision estimates for this value for different alphabet sizes c is the purpose of this publication.
Numerically, the length of the longest common subsequence of two given sequences can be calculated very efficiently using a transfer matrix algorithm. This transfer matrix algorithm calculates the auxiliary quantity ℓ i,j which is defined to be the length of the longest common subsequence of the substrings x 1 . . . x i and y 1 . . . y j . The recursion for ℓ i,j is where This recursion is completed by the initial conditions  Fig. 1. Lattice representation of the longest common subsequence problem. (a) shows how the two sequences ABBBA and AABAB are written at the edges of the lattice. The horizontal bonds of the lattice correspond to matches with a weight one (solid lines) or to mismatches with a weight zero (dashed lines.) The diagonal bonds correspond to omitted letters. Each common subsequence corresponds to a path from the leftmost to the rightmost point of the lattice. The length of the common subsequence is the sum over all weights of the bonds which the path passed. The path shown as an example has a weight of three and corresponds to the maximal common subsequence ABA. The figure also shows how we use the coordinates r and t in order to denote lattice points and how the diamond shaped lattice can be split into two triangular lattices (long dashed line.) (b) shows the rectangular lattice which we use instead of the lattice of (a) in order to be able to handle the effects of the finite lattice size.
The length of the longest common subsequence of the original strings x and y is then L(N ) = ℓ N,N . The recursion equation can be visualized by assigning the ℓ i,j to the nodes of the lattice shown in Fig. 1(a) [18,19]. The horizontal bonds then correspond to the η i,j and the diagonal bonds correspond to omitting a letter from one of the sequences. The recursive algorithm calculates the path from the origin to the end point of this lattice with the largest weight as given by the sum over the bond weights through which the path passes. This is clearly a discrete model of a directed polymer (the path) in a random medium [15] (the random matches and mismatches η i,j .) To make this more explicit, we will use "spatial" and "temporal" coordinates r and t instead of the indices i and j to refer to lattice points as shown in Fig. 1(a). In this coordinate system the dynamics given by the recursive algorithm reads The total length L(N ) = ℓ(0, 2N ) of the longest common subsequence corresponds to the total free energy of the directed polymer. This is clearly an extensive quantity and the proportionality constant, the free energy per length, is the Chvátal-Sankoff constant. It can in principle be calculated numerically by running the algorithm (5) for a large number of sequences and averaging the free energies obtained. As already mentioned the difficulty with this procedure is that the free energy has terms which are subleading in the length N of the sequences. Thus, the ratio L(N ) /N only converges towards the Chvátal-Sankoff constant a c as the sequences become very long. For high precision measurements, the rate of this convergence has to be taken into account for a proper extrapolation towards infinite sequence lengths. This is relatively hard for the diamond shaped lattice, since there is no theoretical understanding of its finite size effects. The only reliable result is a bound [19] on the finite size dependence. Dančík [11] assumed that this bound represents the exact functional form of the finite size correction and used it to fit his numerical data generated from four pairs of sequences of length up to one million to arrive at a value of a c=2 = 0.81225 ± 0.00025 for a two letter alphabet. More recently, Boutet de Monvel tried to extract the finite size behavior directly from the numerical data without any theoretical foundation and concluded L(N ) /N ≈ a c + O(N −1/2 / log N ) which lead him to a value 1 of a c=2 = 0.81233 ± 0.00005 [12,13].

LCS on a rectangular lattice
In light of the confusion on the handling of finite size effects, we will consider a rectangular lattice of a given width W as the one shown in Fig. 1(b). In order to minimize the finite size effects, we apply periodic boundary conditions in the spatial (vertical) direction. For any fixed W the dynamics given by Eq. (5) will after some startup phase become stationary which allows us to measure with nearly arbitrary precision if we use long enough sequences (note also, that in this geometry we have to perform only W N instead of N 2 elementary steps as the one given in Eq. (5) on the diamond shaped lattice which allows for much larger sequence lengths N .) This geometry directly corresponds to the finite size geometry usually imposed in studies of directed polymers in a random medium and equivalent KPZ surface growth problems [20]. From these studies it is well known [21], that with some constant b c . We argue in App. A that i.e., that calculating a c (W ) for fixed W and taking the limit W → ∞ actually yields the Chvátal-Sankoff constant a c . The advantage of this procedure over other numerical approaches is that we know the functional form 1 Boutet de Monvel does not give an actual statistical error of his estimates. Instead he gives three different estimates for the Chvátal-Sankoff constant at each alphabet size. These three values stem from three different ways to treat the finite size effects. The statistical error cited here reflects the spread of these three values.
of the finite size dependence of a c (W ) in advance and can extract the Chvátal-Sankoff constant a c by fitting numerically estimated a c (W ) to the functional form At this point we want to remark for the reader familiar with the surface growth analogy of the LCS problem that in the surface growth language there are two finite size correction formulae known [21]. If the surface grows for a very long time t but is restricted to a width W ≪ t 2/3 Eq. (7) applies. In the opposite regime, i.e., for W ≫ t 2/3 , there is a different scaling behavior which now depends on t instead of W . It appears that the diamond shaped lattice of the original LCS problem is in this transient phase since we have t = 2W . However, the known finite size correction formula in this regime applies only if the surface grows from a flat substrate while the diamond lattice forms a wedged substrate leading to the more difficult finite size effects observed numerically by Boutet de Monvel [12,13]. It turns out, though, that the flat substrate can also be translated into the LCS language: It requires cutting the diamond shaped lattice of size t into two triangles as indicated by the long dashed line in Fig. 1(a), applying the recursion equation (5) with the diamond boundary conditions Eq. (4) within the left triangle, and then calculating It can be shown [19] that lim t→∞ a c (t) = a c and the finite size correction should for this geometry be [21] a c (t) = a c − b c t 2/3 + higher order terms.
This explicit finite size dependence formula could also be used in order to get high precision estimates of the Chvátal-Sankoff constant. However, as we will see below the rectangular geometry is advantageous in terms of the numerical evaluation of the recursion equation (5). Thus, we will use the rectangular geometry in our current study. For a better theoretical understanding of the longest common subsequence problem on the rectangular lattice and in order to formulate a very efficient algorithm for its simulation it is helpful to concentrate on the differences between neighboring ℓ(r, t). In order to preserve the symmetry of the lattice shown in Fig. 1 From the recursion equation (5) it can be easily checked by induction that ∆(r, t) ∈ {0, 1}. They can thus be considered Boolean variables. In terms of these quantities, the recursion equation (5) can be rewritten as for even r + t. Note, that this formulation does not make any reference to the absolute lengths ℓ(r, t) of the longest common subsequences. The dynamics of the LCS problem is thus completely captured by the dynamics of the length differences as given by Eqs. (13) and (14). Every configuration of the ℓ(r, t) can be equally well represented by a configuration of the ∆(r, t). Reversely, a configuration of the ∆(r, t) represents a configuration of the ℓ(r, t), if the consistency condition for the validity of the periodic boundary conditions in ℓ(r, t) is fulfilled. The alternating sum on the left hand side of Eq. (15) is conserved under the dynamics given by Eq. (13) and (14) and is thus always fulfilled, if it is fulfilled for the initial choice of the ∆(r, t = 0). Slaved to the dynamics of the ∆ is the evolution of the average length [ℓ(2k, t) + ℓ(2k+1, t−1)] for t odd of the longest common subsequence which changes by δ(2k, t) for t even δ(2k + 1, t) for t odd (16) with in every time step. Together with Eq. (6) it thus yields a c (W ) = δ(r, t) .
The rewriting of a c (W ) in terms of δ opens the possibility of a very fast implementation of the longest common subsequence problem. We note that Eqs. (13) and (14) transform a pair of length differences into another pair of length differences independent of the other pairs at the same time t. According to the lattice structure shown in Fig. 1(b) this happens for different ways of pairing at different times. If we interpret the ∆(r, t) and η(r, t) as Boolean variables, we can give Eqs. (13) and (14)  Thus, we store 32 of the ∆(r, t) for even r and the corresponding 32 of the ∆(r, t) for odd r simultaneously as the single bits of one integer variable each. 32 of the matchmismatch variables η(r, t) can be stored in the same way. Then, Eqs. (19) and (20) can be performed in parallel on these 64 lattice sites by bitwise logical operations. After these operations the odd sites are shifted by one bit to the right so that they pair up with their new even site partners and the same procedure is repeated. After shifting the odd sites one bit back to the left the algorithm can proceed from the beginning In order to measure a c (W ) we note that the increase δ(r, t) in Eq. (16) is given by the Boolean equation and can thus also be easily calculated for 32 pairs of sites with two bitwise or operations. A bit-count then gives the value of a c (W ) after averaging over many time steps and configurations of the disorder η(r, t).

First passage percolation
We verify the algorithm and the finite size behavior given by Eq. (9) on the first passage percolation version of the LCS problem. For this system we are not only able to prove explicitly the scaling form Eq. (9) but we can calculate the full finite size correction and specifically the prefactor b c of its leading term. The first passage percolation version of the LCS problem also obeys the dynamics given by Eqs. (13) and (14). The only difference is, that instead of choosing random sequences x 1 . . . x N and y 1 . . . y N and calculating the local matches η(r, t) from these sequences, we use the variables η(r, t) which are taken to be independent identically distributed random variables with η(r, t) = 1 with probab. 1/c 0 with probab. 1 − 1/c .
The analog a c of the Chvátal-Sankoff constant for this problem is known to be a c = 2/( √ c + 1) which had been conjectured by Arratia for the a c of the LCS problem. This result follows, e.g., as a consequence of an exact mapping [22] between the LCS problem and the discrete time asymmetric exclusion process [23,24], a well studied exactly solvable model of the KPZ surface growth universality class. (The mapping basically interprets the length differences ∆(r, t) as the site occupation numbers of the asymmetric exclusion process.) Below, we will derive the result a c = 2/( √ c+1) and its finite size correction without explicit reference to this mapping.
Eqs. (19) and (20) can be interpreted in terms of a pair (∆(r − 1, t − 1), ∆(r, t − 1)) ∈ {(0, 0), (0, 1), (1, 0), (1, 1)} mapped onto another pair (∆(r − 1, t), ∆(r, t)) ∈ {(0, 0), (0, 1), (1, 0), (1, 1)} with probabilities depending on the possible values of η(r, t). This mapping can be written as the matrix in the basis |00 , |01 , |10 , |11 . A distribution of possible states of the system can be interpreted as a normalized vector |ψ in the 2 2W dimensional space of all possible configurations of the 2W variables ∆(r, t) at a fixed time. In a time step with even t, each neighboring pair of length differences is transformed according to the matrix T 0 . Thus, the whole state distribution |ψ is transformed into the vector T |ψ with At odd time steps the pairing of the length differences is different. In order to describe the transformation at odd time steps, we introduce the translation operator C, which shifts all length differences ∆(r, t) by one spatial position to the right, i.e., The time evolution at odd times is then given by a shift of all length differences to the left, application of the even time evolution operator T and a shift of all length differences back to the right, i.e., by CT C −1 . After two time steps, the state vector |ψ is thus transformed into the state vector CT C −1 T |ψ . The stationary state is the eigenvector |ψ 0 of CT C −1 T with the eigenvalue one which is consistent with the condition (15). It is easy to check, that this eigenvector is given by (26) with the combinatorial normalization factor where P W is the Legendre polynomial of degree W . Since CT C −1 T restricted to the subspace of state vectors consistent with condition (15) is irreducible and neither the eigenvector |ψ 0 nor CT C −1 T have any negative entries, it is the unique stationary state of the system according to the Perron Frobenius theorem [25]. The analog a c (W ) of the Chvátal-Sankoff constant for this modified system can be calculated from the knowledge of this stationary state via Eqs. (18) and (21). Since η(r, t) is uncorrelated from ∆(r − 1, t − 1) and ∆(r, t − 1) we get a c (W ) = η(r, t) ∨ ∆(r, t − 1) ∨ ∆(r − 1, t − 1) The probability that two neighboring length differences vanish simultaneously can be directly calculated from the explicitly known stationary state Eq. (26). Since fixing a pair of the length differences to zero still leaves all the possibilities to the W − 1 remaining pairs, it is Inserting this into Eq. (28) yields the full finite size dependence of the first passage percolation version of the LCS problem in terms of Legendre polynomials. Expanding these Legendre polynomials for large degrees W finally yields the first order terms of this exact finite size correction. This can be directly compared to the numerical results obtained by the multi-spin coding algorithm described above. To this end we choose 1, 000 random initial conditions of the ∆(r, t = 0) (that fulfil Eq. (15)) and the same number of random configurations of the η(r, t). Then, we proceed as described at the end of Sec. 3, i.e., we apply the recursion equations (19) and (20)  An important question is how close these estimates of a c (W ) come to its true value. In answering this question, we have to consider statistical and systematic deviations. The statistical deviations can be measured by looking at the sample-to-sample fluctuations between the different configurations of the disorder η(r, t) and made as small as we wish by increasing the number of disorder configurations and the number of recursion steps we average over. The systematic deviations have to be studied more carefully. They arise because the Markov dynamics of the differences ∆(r, t) reaches its stationary state only in the limit of infinitely many recursion steps if we start from a random initial state. For a finite number t 1 of recursions steps there is a systematic correction that decays exponentially in t 1 with some decay "time" t 0 .
In order to verify if this exponential approach to the stationary state plays a role in our numerics, we iterate Eqs. (19) and (20) 10 7 times for each configuration of the disorder η(r, t) and calculate 10 different estimates of a c (W ) by averaging in Eq. (18) over t ∈]t 1 , t 1 + 10 6 ] for t 1 ∈ {0, 10 6 , 2 · 10 6 , . . . , 9 · 10 6 }. If there is a systematic deviation this should manifest itself in a systematic dependence of these estimates on the number t 1 of recursion steps performed before the averaging starts.
Since the approach to the stationary state has to become the slower the wider the lattice we have to study this effect for the largest width W = 4096 we plan on using in our numerics. Fig. 2(a) shows the ten estimates of a 2 (W = 4096) which are obtained as described above. Clearly, there is no noticeable systematic dependence on the number t 1 of recursion steps. All fluctuations of the individual points are within the statistical uncertainties of each other. While the statistical uncertainties of the individual points are already on the order of ±10 −6 we can further improve them by averaging over all the points. To be absolutely certain that the approach to the stationary state does not influence our result, we take this average only over the last nine points, i.e., we average over all t ∈]10 6 , 10 7 ]. This average is indicated as the dashed line in Fig. 2(a). After we have convinced ourselves, that we can estimate the a c (W ) to within a precision of ±10 −6 for all W , we can study the dependence of a c (W ) on the width W of the lattice. Fig. 3(a) shows these numerically obtained values of a 2 (W ) for an alphabet of size c = 2 as a function of 1/W . The points clearly fall on a straight line over the whole range of lattice widths from W = 128 to W = 4096. A simple least square fit to a straight line yields (31) This has to be compared to the exact results We conclude that the value for infinite system size is extremely well reproduced by taking into account the 1/W finite size correction. Even the prefactor of the finite size correction can be extracted with a reasonably high precision, although the error of the fit for the finite size coefficient as given in Eq. (31) underestimates the true error. This is to be expected since the finite size coefficient itself is subject to further finite size corrections which yield an additional systematic error in its estimation. shows the values a2(W ) for the true longest common subsequence problem including the disorder correlations. Here, the dashed and dotted lines show the upper and lower bounds for the infinite system given by Dančík [11] and Boutet de Monvel [12,13] respectively.

The Chvátal-Sankoff constant
In order to get a good numerical estimate of the real Chvátal-Sankoff constant, we perform the same simulations for the subtly correlated disorder η(r, t) generated from pairs of randomly chosen sequences. In the presence of these disorder correlations, the dynamics of the ∆(r, t) at a given width W can still be interpreted as a Markov process. However, the applicable state space comprises at a given t the ∆(r, t) for r ∈ {0, . . . , 2W − 1} and the last W letters chosen in each of the two sequences. It is much larger than in the first passage percolation version. Thus, although the dynamics still converges exponentially to the stationary state, the initial phase can be much longer than in the first passage percolation case and more care has to be taken to minimize the systematic error of numerical estimates introduced by this effect. Again, we collect estimates from 1, 000 pairs of random sequences and apply the recursion equations (19) and (20) 10 7 times for each sequence pair. Then, we generate the same 10 estimates of a 2 (W = 4096) as in Sec. 4 for the largest width W = 4096 we plan to use in our simulations. Fig. 2(b) shows the dependence of these estimates on the number t 1 of recursion steps performed before starting the averaging. We note two important differences to the first passage percolation case: (i) The estimate with t 1 = 0 is significantly different from the estimates with t 1 ≥ 10 6 and (ii) the individual statistical fluctuations are larger than in the first passage percolation case (note the difference in scale between Figs. 2(a) and (b).) Both findings are to be expected due to the slower approach to the stationary state. Since the first estimate is different from the other nine we conclude that the characteristic number of steps t 0 necessary to approach the stationary state is smaller than but comparable to 10 6 . This slow decorrelation property also renders the average over many recursion steps less effective yielding the larger statistical fluctuations which we observe. These statistical fluctuations are of the order of ±3.5 · 10 −6 . Since the systematic deviation of the estimate for t 1 = 10 6 is already smaller than that and since the characteristics number of steps t 0 is smaller than 10 6 , we can be sure that the systematic deviations of all points with t 1 ≥ 2 · 10 6 are less than 10 −6 due to the exponential decay of these deviations. Then, averaging in Eq. (18) over all t ∈]2 · 10 6 , 10 7 ] yields estimates of a c (W ) with a statistical and systematic error of ±10 −6 .
The results of this procedure for all finite system sizes W are shown in Fig. 3(b). In addition to the larger statistical error bars of the individual points slight corrections to the 1/W behavior are visible for W < 160. Nevertheless, we get a good fit to a straight line in the regime W ≥ 160 with the result a 2 (W ) ≈ (0.812653 ± 0.000004) − (0.0520 ± 0.0012) 1 W .
(32) Varying the fitting range towards larger W changes the infinite W value of the measured Chvátal-Sankoff constant only within the quoted error bars. This result is significantly larger than the results of Dančík [11] and of Boutet de Monvel [12,13] obtained for 4 lattices of size up to 10 6 × 10 6 and 10, 000 lattices of size 10 4 × 10 4 respectively. As shown in Fig. 3(b) the value of the finite width Chvátal-Sankoff constant already significantly exceeds their estimates of the infinite system size value at moderate W ≈ 256.
In the same way we get high precision values for the Chvátal-Sankoff constant for larger alphabet sizes c. However, the finite size corrections for larger alphabet size are larger and fits to a linear law only settle to within the statistical error estimate for W ≥ 352. The fitted values are summarized in Tab. 1. While our method produces estimates with a much higher precision than the traditional method due to the fact that we know the form of the finite size dependence, all our estimates for c ≥ 4 are consistent with Boutet de Monvel's within his variations between different assumed finite size corrections [12]. We observe that the differences between the Chvátal-Sankoff constant a c and its counterpart a c for the uncorrelated disorder are significant but become smaller with increasing alphabet size. This is to be expected intuitively since the correlations between the η(r, t) become weaker with increasing alphabet size (if we know the letter in one sequence and the information that we have a mismatch this fixes the letter in the other sequence only up to c − 1 possible choices.) This dependence on the alphabet size is also consistent with the fact that it apparently becomes more difficult to take the correlations into account numerically and to get good numerical estimates of the a c as the alphabet size decreases. This materializes in the discrepancies between our high precision results for a 2 and earlier estimates of the Chvátal-Sankoff constant which are not present for the larger alphabet sizes.  Table 1. Numerical values for the Chvátal-Sankoff constant ac and its finite size correction bc for different alphabet sizes c. The errors in parentheses are statistical errors on the last digit. For comparison the counterpart ac = 2/( √ c + 1) of the Chvátal-Sankoff constant for first-passage percolation is also given.

Conclusions
We conclude that in order to get numerical values of the Chvátal-Sankoff constant with a high precision a proper handling of the finite size effects is absolutely necessary. We showed how concepts from statistical physics can help to tackle this problem. We moreover presented a highly effective multi-spin coding scheme which further increases the precision of the simulations. The numerical results given will be valuable in guiding and evaluating theoretical approaches to understand the small but noticeable effect of the subtle disorder correlations which are responsible for the difference between the Chvátal-Sankoff constant and its counterpart in the first-passage percolation problem.

A Change of lattice
In this appendix we will argue that the limiting quantity defined on the diamond shaped lattice shown in Fig. 1(a).
To this end, we first consider a path from the left edge of the rectangular lattice to the point (W −1, 2t) as indicated in Fig. 4(a) which is the optimal path in each of the diamonds. Clearly, ℓ(W − 1, 2t) can only be larger than the number of matches along this specific path which implies Fig. 4. Relation between optimal paths on the rectangular and the diamond shaped lattice. (a) shows how a good path for the rectangular lattice can be constructed by stringing together optimal paths on diamond shaped lattices of size W ×W . In (b) a good path for a diamond shaped lattice of size (t + W ) × (t + W ) is constructed from the optimal path on the rectangular lattice. The left end of the path is connected to the tip of the diamond which can only increase the number of matches. For each time the optimal path wraps around the periodic boundary conditions the path has to be modified as shown by the diagonal dashed line. For each such event, at most W matches along the solid path can be missed.
or after dividing both sides by t and taking the limit of t → ∞ a c (W ) ≥ L(W ) W .
Taking the limit W → ∞ of this inequality yields a c (∞) ≥ a c .
On the other hand, let us consider the best path from the left edge of the rectangular lattice to the point (W − 1, 2t), i.e., the path with ℓ(W −1, 2t) matches. As shown in Fig. 4(b), we can construct a path which connects the two end points in a diamond shaped lattice of size (t + W ) × (t + W ) from this path. Since the length of the longest common subsequence of the two associated sequences of length t + W can only be longer than the common subsequence corresponding to this path we get where n wrap (t) is the number of times that the best path from the left edge to (W − 1, 2t) "wraps around" the periodic boundary conditions. Dividing by t yields t + W t which in the limit t → ∞ leads to a c ≥ a c (W ) − W lim t→∞ n wrap (t) t .
From the analogy with the directed polymer in a random medium it is well known that the displacement of a typical optimal path of length t scales like t 2/3 [15,20,26,27].
Therefore, if we take the limit W → ∞ in Eq. (40) the second term on the right hand side vanishes and we are left with a c ≥ a c (∞).
(42) Together with Eq. (37) this establishes the equality between the infinite width limit of the a c (W ) and the Chvátal-Sankoff constant a c .