Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Use a smarter algorithm for xbt_str_diff.
authorArnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Wed, 18 Apr 2012 15:39:39 +0000 (17:39 +0200)
committerArnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Fri, 20 Apr 2012 07:25:19 +0000 (09:25 +0200)
The previous one had a time and space complexity of O(n.m), with n and m
being the length of the inputs, and reached the memory limits pretty fast.

Implement the algorithm described in "An O(NP) Sequence Comparison Algorithm",
by Sun Wu, Udi Manber, Gene Myers, and Webb Miller (Information Processing
Letters 35(6):317-323, 1990), with the linear-space divide-and-conquer
strategy described in "An O(ND) Difference Algorithm and Its Variations",
by Eugene W. Myers (Algorithmica 1:251-266, 1986).


No differences found