A common basis for similarity measures involving two stringsFootnote†

†Partially supported by the National Science Foundation Grant No. ECS-80-0904L.

References

• Aho , A.V. , Hirschberg , D.S. and Ullman , J.D. 1976 . Bounds on the complexity of the longest common subsequence problem . J-ACM , 23 : 1 – 12 .
   Web of Science ®Google Scholar
• Aho , A.V. , Hopcroft , J.E. and Ullman , J.D. 1974 . The Design and Analysis of Computer Algorithms , Reading, Mass : Addison-Wesley .
   Google Scholar
• Hirschberg , D.S. 1977 . Algorithms for the longest common subsequence problem . J-ACM , 24 : 664 – 675 .
   Web of Science ®Google Scholar
• Hirschberg , D.S. 1975 . A linear space algorithm for computing maximal common subsequences . C-ACM , 18 : 341 – 343 .
   Web of Science ®Google Scholar
• Hunt , J.W. and Szymanski , T.G. 1977 . A fast algorithm for computing longest common subsequences . C-ACM , 20 : 350 – 353 .
   Web of Science ®Google Scholar
• Kashyap , R.L. and Oommen , B.J. 1977 . Similarity measures for sets of strings . Int. Journal of Comp. Math , 12 To appear in the
   Google Scholar
• Levenshtein , A. 1966 . Binary codes capable of correcting deletions, insertions and reversals . Sov. Phy. Dokl , 10 : 707 – 710 .
   Google Scholar
• Maclane , S. and Birkhoff , G. 1967 . Algebra , New York : The Macmillan Company .
   Google Scholar
• Maier , D. 1978 . The complexity of some problems on subsequences and supersequences . J-ACM , 25 : 322 – 336 .
   Web of Science ®Google Scholar
• Masek , W.J. and Paterson , M.S. 1980 . A faster algorithm computing string edit distances . J. of Comp, and Syst. Sei , 20 : 18 – 31 .
   Web of Science ®Google Scholar
• Needleman , S.B. and Wunsch , C.D. 1970 . A general method applicable to the search for similarities in the amino acid sequence of two proteins . J. Mol. Biol , 20 : 443 – 453 .
   Web of Science ®Google Scholar
• Okuda , T. , Tanaka , E. and Kasai , T. 1976 . A method of correction of garbled words based on the Levenshtein metric . IEEE Trans, Comp , C-25 : 172 – 177 .
   Web of Science ®Google Scholar
• Seller , P.H. 1974 . An algorithm for the distance between two finite sequences . J. of Combinatorial Theory , 16 : 253 – 258 .
   Google Scholar
• Wagner , R.A. and Fischer , M.J. 1974 . The string to string correction problem . J-ACM , 21 : 168 – 173 .
   Web of Science ®Google Scholar
• Wong , C.K. and Chandra , A.K. 1976 . Bounds for the string editing problem . J-ACM , 23 : 13 – 16 .
   Web of Science ®Google Scholar