There's more than one way to do things | |
PerlMonks |
Re^6: Suffix-prefix matching done right (updated)by LanX (Saint) |
on Nov 06, 2021 at 16:06 UTC ( [id://11138511]=note: print w/replies, xml ) | Need Help?? |
> at least O(N^2) A disagree, rather at most O(N*log N) for base64 input and a given max distance.
My algorithm based on Re: Suffix-prefix matching done right correctly calculated 1million overlaps with up to 6 errors in You just have to avoid impossible matches right from the beginning and to bail out with the longest match. Nobody needs all Levenshtein distances for all combinations. Parameters:
updatesorry> Took: 53.5716695785522 I forgot a bail-out flag. I'll try now strings with 2000 bytes ...
update
as I said, it's still tuned for correctness not for performance
Cheers Rolf
In Section
Seekers of Perl Wisdom
|
|