|
|
|
|
|
|
by Robin_Message
3365 days ago
|
|
|
There is: https://en.wikipedia.org/wiki/Longest_common_subsequence_pro... which is what most diff tools use. It is a simple and clear algorithm with no special cases once you get your head around it. It works in O(NxM) time, which seems like a reasonable lower bound (you need to compare everything to everything else to have a chance of getting the best alignment) although there are ways to do better with constraints. (I remember one for gene alignment which broke N and M in two, recurse 4 times on each pairing, and then had a quick-ish way to put those together again. Can't remember the details though!) |
|
|