Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re^7: Suffix-prefix matching done right (updated)

by NERDVANA (Pilgrim)
on Nov 06, 2021 at 18:24 UTC ( #11138518=note: print w/replies, xml ) Need Help??


in reply to Re^6: Suffix-prefix matching done right (updated)
in thread Suffix-prefix matching done right

OP said it could also be deletions and insertions. So the xor trick won't work. Without more information from OP, we can only guess, but I was guessing this was a genetics problem trying to build DNA sequences from fragments, and the mention of base64 was just mock data to test the algorithm. If the data can have random insertions, deletions, and swaps, then you need the full DP algorithm. *IF* the number of acceptable errors is low, then yes you can short-circuit it and maybe end up close to linear, but then there's stil the added complexity of deciding how much overlap gives the best result.
  • Comment on Re^7: Suffix-prefix matching done right (updated)

Replies are listed 'Best First'.
Re^8: Suffix-prefix matching done right (updated)
by LanX (Sage) on Nov 06, 2021 at 18:35 UTC
    > OP said it could also be deletions and insertions.

    Did he?

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery

      Hm. I guess that was also part of my assumption about it being a genetics problem.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11138518]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (7)
As of 2022-01-21 17:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (59 votes). Check out past polls.

    Notices?