×
Masek, William J.; Paterson, Michael S.

A faster algorithm computing string edit distances. (English) Zbl 0436.68044

J. Comput. Syst. Sci. 20, 18-31 (1980).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0436.68044

Cited in 1 Review
Cited in 150 Documents

MSC:

68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity

Keywords:

edit distance; character strings; longest common subsequence
Cite Review PDF
Full Text: DOI

References:

[1] Aho, A. V.; Hirschberg, D. S.; Ullman, J. D., Bounds on the complexity of the longest common subsequence problem, J. Assoc: Comput. Mach., 23, No. 1, 1-12 (1976) · Zbl 0316.68027
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0286.68029
[3] Soviet Math. Dokl., 11, No.5, 1209-1210 (1970) · Zbl 0214.23601
[4] Hirschberg, D. S., A linear space algorithm for computing maximal common subsequences, CACM, 18, No. 6, 341-343 (1975) · Zbl 0301.68042
[5] Hopcroft, J. E.; Paul, W. J.; Valiant, L. G., On time versus space and other related problems, (Proceedings, 16th Annual Symposium on Foundations of Computer Science. Proceedings, 16th Annual Symposium on Foundations of Computer Science, Berkeley (1975)), 57-64
[6] Lowbance, R.; Wagner, R. A., An extension of the string to string correction problem, J. Assoc. Comput. Mach., 22, No. 2, 177-183 (1975) · Zbl 0301.68028
[7] Wagner, R. A.; Fischer, M. J., The string to string correction problem, J. Assoc. Comput. Mach., 21, No. 1, 168-183 (1974) · Zbl 0278.68032
[8] Wong, C. K.; Chandra, A. K., Bounds for the string editing problem, J. Assoc. Comput. Mach., 23, No. 1, 13-16 (1976) · Zbl 0316.68019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.