References

1

A. V. Aho, D. S. Hirschberg, and J. D. Ullman. Bounds on the complexity of the longest common subsequence problem. J. ACM, 23:1-12, 1976.

2

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Pu. Co., Reading, MA, 1974.

3

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley Pu. Co., Reading, MA, 1983.

4

L. Allison and T. I. Dix. A bit string longest common subsequence algorithm. Inf. Process. Lett., 23:305-310, 1986.

5

A. Apostolico. Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings. Inf. Process. Lett., 23:63-69, 1986.

6

A. Apostolico. Remark on the Hsu-Du new algorithm for the longest common subsequence problem. Inf. Process. Lett., 25:235-236, 1987.

7

A. Apostolico and C. Guerra. The longest common subsequence problem revisited. Algorithmica, 2:315-336, 1987.

8

R. M. Baer and P. Brock. Natural sorting over permutation spaces. Math. Comp., 22:385-410, 1968.

9

V. Chvátal, D. A. Klarner, and D. E. Knuth. Selected combinatorial research problems. Technical Report STAN-CS-72-292, Computer Science Department, Stanford University, 1972.

10

V. Chvátal and D. Sankoff. Longest common subsequences of random sequences. Technical Report STAN-CS-75-477, Computer Science Department, Stanford University, 1975.

11

V. Chvátal and D. Sankoff. Longest common subsequences of two random sequences. J. Appl. Prob., 12:306-315, 1975.

12

M. Crochemore. Longest common factor of two words. In Proceedings of CAAP'87, Pisa, Italy, pages 26-36, 1987.

13

J. Deken. Some limit results for longest common subsequences. Discrete Math., 26:17-31, 1979.

14

M. L. Fredman. On computing the length of longest increasing subsequences. Discrete Math., 11:29-35, 1975.

15

J. Gallant, D. Maier, and J. A. Storer. On finding minimal length superstrings. J. Comput. Syst. Sci., 20:50-58, 1980.

16

P. A. V. Hall and G. R. Dowling. Approximate string matching. ACM Comput. Surv., 12:381-402, 1980.

17

J. J. Hebrard. Distances sur les mots. Application à la recherche de motifs. Thèse de 3e cycle, Université de Haute-Normandie, 1984.

18

P. Heckel. A technique for isolating differences between files. Commun. ACM, 21:264-268, 1978.

19

D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Commun. ACM, 18:341-343, 1975.

20

D. S. Hirschberg. Algorithms for the longest common subsequence problem. J. ACM, 24:664-675, 1977.

21

D. S. Hirschberg. An information theoretic lower bound for the longest common subsequence problem. Inf. Process. Lett., 7:40-41, 1978.

22

D. S. Hirschberg and L. L. Larmore. The set lcs problem. Algorithmica, 2:91-95, 1987.

23

W. J. Hsu and M. W. Du. New algorithms for the LCS problem. J. Comput. Syst. Sci., 29:133-152, 1984.

24

J. W. Hunt and M. D. McIlroy. An algorithm for differential file comparison. Technical Report #41, Computing Science, Bell Laboratories, 1976.

25

J. W. Hunt and T. G. Szymanski. A fast algorithm for computing longest common subsequences. Commun. ACM, 20:350-353, 1977.

26

D. E. Knuth. The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley Pu. Co., Reading, MA, 1973.

27

R. Lowrance and R. A. Wagner. An extension of the string-to-string correction problem. J. ACM, 22:177-183, 1975.

28

D. Maier. The complexity of some problems on subsequences and supersequences. J. ACM, 25:322-336, 1977.

29

W. J. Masek and M. S. Paterson. A faster algorithm computing string edit distances. J. Comput. Syst. Sci., 20:18-31, 1980.

30

K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin, 1984.

31

W. Miller and E. W. Myers. A file comparison program. Software - Practice and Experience, 15:1025-1040, 1985.

32

A. Mukhopadhyay. A fast algorithm for the longest common subsequence problem. Information Sciences, 20:69-82, 1980.

33

N. Nakatsu, Y. Kambayashi, and S. Yajima. A longest common subsequence algorithm suitable for similar text strings. Acta Inf., 18:171-179, 1982.

34

S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Molecular Biology, 48:443-453, 1970.

35

Y. Robert and M. Tchuente. A systolic array for the longest common subsequence problem. Inf. Process. Lett., 21:191-198, 19885.

36

D. Sankoff. Matching sequences under deletion/insertion constraints. Proc. Nat. Acad. Sci. U.S.A., 69:4-6, 1972.

37

D. Sankoff and J. B. Kruskal. Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison. Addison-Wesley Pu. Co., Reading, MA, 1983.

38

S. M. Selkow. The tree to tree editing problem. Inf. Process. Lett., 6:184-186, 1977.

39

P. H. Sellers. An algorithm for the distance between two finite sequences. J. Comb. Th. A, 16:253-258, 1974.

40

P. H. Sellers. On the theory and computation of evolutionary distances. SIAM J. Appl. Math., 26:787-793, 1974.

41

P. H. Sellers. The theory and computation of evolutionary distances: pattern recognition. J. of Algorithms, 1:359-373, 1980.

42

T. G. Szymanski. A special case of the maximal common subsequence problem. Technical Report TR-170, Computer Science Lab., Princeton University, 1975.

43

W. F. Tichy. The string-to-string correction problem with block moves. ACM Trans. Comput. Syst., 2:309-321, 1984.

44

S. M. Ulam. Some combinatorial problems studied experimentally on computing machines. In S. K. Zaremba, editor, Applications of Number Theory to Numerical Analysis, pages 1-3, apa, 1972. Academic Press.

45

T. K. Vintsyuk. Speech discrimination by dynamic programming. Kibernetika, 4:81-88, 1968.

46

R. A. Wagner and M. J. Fischer. The string-to-string correction problem. J. ACM, 21:168-173, 1974.

47

C. K. Wong and A. K. Chandra. Bounds for the string editing problem. J. ACM, 23:13-16, 1976.