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

Longest common substring with N mismatches

by Anonymous Monk
on Sep 11, 2017 at 16:24 UTC ( #1199128=perlquestion: print w/replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi everyone!
I am in need on an implementation of the Longest-Common-Substring problem, but with one addition - that one can allow for N mis-matches. I found several threads in the Monastery, but they all seem to work for exact matches - no miscmatches allowed.
Anybody knows where to look for?
Many thanks!
  • Comment on Longest common substring with N mismatches

Replies are listed 'Best First'.
Re: Longest common substring with N mismatches
by poj (Prior) on Sep 11, 2017 at 17:36 UTC

      It was buggy, but now it's fixed. Also, it now returns all matches instead of just one (still in O(M*N) time).

        Ikegami, that is indeed precisely what I was after.
        One small question, if you may:
        Is there a way that I can know which part (beg-end) of each of the two strings I provide is covered by the LCSS?
        Many thanks!
Re: Longest common substring with N mismatches
by tybalt89 (Curate) on Sep 11, 2017 at 16:35 UTC

    Please define "mismatch". Does it include inserts and deletes and replaces? Or only replaces?

      Replaces only.
Re: Longest common substring with N mismatches
by LanX (Bishop) on Sep 11, 2017 at 16:46 UTC
      All I am asking is if anyone knows of such a module or implementation. I read threads like 994837, 608174, 249239, 145608, but they all work with exact matching. And I was hoping that someone would perhaps know of a module or something that can allow for some mismatches instead of requiring exact matches.
Re: Longest common substring with N mismatches
by hdb (Monsignor) on Sep 12, 2017 at 06:29 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1199128]
Approved by Marshall
help
Chatterbox?
LanX .oO( cemetery breweries ? )

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (9)
As of 2017-12-15 11:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (431 votes). Check out past polls.

    Notices?