HIRSCHBERG’S ALGORITHM FOR APPROXIMATE MATCHING

Adam Drozdek

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.


Full Text:

PDF

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




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

Refbacks

  • There are currently no refbacks.