HIRSCHBERG’S ALGORITHM FOR APPROXIMATE MATCHING
DOI:
https://doi.org/10.7494/csci.2002.4.1.3601Abstract
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
