Re^5: Longest common substring with N mismatches


Just another Perl shrine
	PerlMonks

Re^5: Longest common substring with N mismatches

by LanX (Saint)

on Sep 11, 2017 at 17:05 UTC ( [id://1199136]=note: print w/replies, xml )

Need Help??

in reply to Re^4: Longest common substring with N mismatches
in thread Longest common substring with N mismatches

N-mer???

Are you looking for Levenshtein distance ?

If not please be so kind and provide us an example with input and desired output.

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)

Je suis Charlie!}

Comment on Re^5: Longest common substring with N mismatches

Replies are listed 'Best First'.
Re^6: Longest common substring with N mismatches by Anonymous Monk on Sep 11, 2017 at 17:09 UTC
Sorry, I meant to write k-mer before :) One example could be the following (using also the node you mentioned as input): `$str1='AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'; $str2='RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRAAAA +AAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAABAAZZZZZZZ';` [download] In this case, the whole `$str1` should much because it only has 1 mismatch (assuming the user sets the allowed #mismatches to 1) and not only the AAAAA before the B.	[reply] [d/l] [select]
Re^7: Longest common substring with N mismatches by LanX (Saint) on Sep 11, 2017 at 17:17 UTC
Looks like the same solution fits, xor both strings at different positions and count the longest runs of zeros tolerating n non zeros in between, probably with a composed regex. See ^ in perlop#Bitwise-Or-and-Exclusive-Or Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Je suis Charlie!}	[reply]
Re^7: Longest common substring with N mismatches by Anonymous Monk on Sep 11, 2017 at 17:14 UTC
Yeah, that sounds like How do you match a stretch of at least N characters, looks like you two are doing the same homework problem	[reply]

In Section Seekers of Perl Wisdom

Log In^?

Domain Nodelet^?

www.com | www.net | www.org

Node Status^?

node history
Node Type: note [id://1199136]
help

Chatterbox^?

How do I use this? • Last hour • Other CB clients

Other Users^?

Others imbibing at the Monastery: (3)

As of 2024-04-24 20:22 GMT

Sections^?

Information^?

Find Nodes^?

Leftovers^?

Today I Learned

Voting Booth^?

No recent polls found