|XP is just a number|
Re^6: Suffix-prefix matching done right (updated)by LanX (Sage)
|on Nov 06, 2021 at 16:06 UTC||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.
> Took: 53.5716695785522
I forgot a bail-out flag.
I'll try now strings with 2000 bytes ...
as I said, it's still tuned for correctness not for performance