HIRSCHBERG’S ALGORITHM FOR APPROXIMATE MATCHING

Authors

  • Adam Drozdek AGH University of Science and Technology

DOI:

https://doi.org/10.7494/csci.2002.4.1.3601

Abstract

The Hirschberg algorithm was devised to solve the longest common subsequence problem. The paper discusses the way o f adopting the algorithm to solve the string matching problem in linear space to determine edit distancefor two strings and their alignment.

Downloads

Download data is not yet available.

References

CrochemoreM.,RytterW.:Textalgorithms.NewYork,OxfordUniversityPress1994

GusfieldD.:Algorithmsonstrings,trees,andseąuences.NewYork,CambridgeUniversityPress1997

HirschbergD.S.:Alinear-spacealgorithmforcomputingmaximalcommonsubseąuences.Com

munications of the ACM, 18, 1975, 341-343

Stephen G.A.: String searching algorithms. Singapore, World Scientific 1994

Wagner R.A., Fischer M.J.: The string-to-string correction problem. Journal of the ACM, 21,

, 168-173

Downloads

Published

2020-01-02

How to Cite

Drozdek, A. (2020). HIRSCHBERG’S ALGORITHM FOR APPROXIMATE MATCHING. Computer Science, 4(1). https://doi.org/10.7494/csci.2002.4.1.3601

Issue

Section

Articles