3 ms·
If edit distance is bounded there appear to be algorithms that are linear in the input size: http://en.wikipedia.org/wiki/Edit_distance http://en.wikipedia.org
by GFK_of_xmaspast 12y ago
If edit distance is bounded there appear to be algorithms that are linear in the input size:
http://en.wikipedia.org/wiki/Edit_distance http://en.wikipedia.org/wiki/Edit_distance
and
http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht...