The longest common subsequence problem revisited
Tóm tắt
Từ khóa
Tài liệu tham khảo
A. V. Aho, D. S. Hirschberg, and J. D. Ullman, Bounds on the complexity of the maximal common subsequence problem,J. Assoc. Comput. Mach.,23 (1976), 1–12.
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1976
A. Apostolico, Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings,Inform. Process. Lett.,23 (1986), 63–69.
A. Apostolico and C. Guerra, A fast linear space algorithm for computing longest common subsequences,Proceedings of the 23rd Allerton Conference, Monticello, IL, 1985, pp. 76–84.
J. L. Bentley and A. C.-C. Yao, An almost optimal algorithm for unbounded searching,Inform. Process. Lett.,5 (1976), 82–87.
M. R. Brown, and R. E. Tarjan, A representation of linear lists with movable fingers,Proceedings of the Wth Annual ACM Symposium on Theory of Computing, San Diego, CA, 1978, pp. 19–29.
D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences,Comm. ACM,18 (1975), 341–343.
D. S. Hirschberg, Algorithms for the longest common subsequence problemJ Assoc. Comput. Mach.,24 (1977), 664–675.
W. J. Hsu and M. W. Du, New algorithms for the LCS problem,J. Comput. System Sci.,29 (1984), 133–152.
J. W. Hunt and T. G. Szymanski, A fast algorithm for computing longest common subsequences,Comm. ACM,20 (1977), 350–353.
H. M. Martinez (ed.), Mathematical and computational problems in the analysis of molecular sequences,Bull. Math. Biol,46, 4 (1984).
W. J. Masek and M. S. Paterson, A faster algorithm for computing string editing distances,J. Comput. System Sci.,20 (1980), 18–31.
K. Mehlhorn,Data Structures and Algorithms 1: Sorting and Searching, EATCS Monographs on TCS, Springer-Verlag, Berlin, 1984.
D. Sankoff and J. B. Kruskal (eds.),Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparisons, Addison-Wesley, Reading, MA, 1983.
P. van Emde Boas, Preserving order in a forest in less than logarithmic time and linear space,Inform. Process. Lett.,6 (1977), 80–82.