Longest common substring with N mismatches

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 (Abbot) on Sep 11, 2017 at 17:36 UTC
Anybody knows where to look for? ikegami replied to a similar question here https://stackoverflow.com/questions/6258922/efficient-substring-matching-in-perl poj	[reply]
Re^2: Longest common substring with N mismatches by ikegami (Patriarch) on Sep 11, 2017 at 21:41 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).	[reply]
Re^3: Longest common substring with N mismatches by Anonymous Monk on Sep 12, 2017 at 09:49 UTC
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!	[reply]
Re^4: Longest common substring with N mismatches by ikegami (Patriarch) on Sep 12, 2017 at 15:51 UTC
Re^5: Longest common substring with N mismatches by leo1982 (Initiate) on Sep 13, 2017 at 08:47 UTC
Some notes below your chosen depth have not been shown here
Re: Longest common substring with N mismatches by tybalt89 (Monsignor) on Sep 11, 2017 at 16:35 UTC
Please define "mismatch". Does it include inserts and deletes and replaces? Or only replaces?	[reply]
Re^2: Longest common substring with N mismatches by Anonymous Monk on Sep 11, 2017 at 16:37 UTC
Replaces only.	[reply]
Re: Longest common substring with N mismatches by LanX (Saint) on Sep 11, 2017 at 16:46 UTC
Homework? How do you match a stretch of at least N characters Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Je suis Charlie!}	[reply]
Re^2: Longest common substring with N mismatches by Anonymous Monk on Sep 11, 2017 at 16:51 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.	[reply]
Re^3: Longest common substring with N mismatches by LanX (Saint) on Sep 11, 2017 at 16:53 UTC
Whats wrong with the link I gave you? see also How do I post a question effectively? Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Je suis Charlie!}	[reply]
Re^4: Longest common substring with N mismatches by Anonymous Monk on Sep 11, 2017 at 17:00 UTC
Re^5: Longest common substring with N mismatches by LanX (Saint) on Sep 11, 2017 at 17:05 UTC
Some notes below your chosen depth have not been shown here
Re: Longest common substring with N mismatches by hdb (Monsignor) on Sep 12, 2017 at 06:29 UTC
How about the following threads: Calculating the number of possible matches with N mismatches for DNA? [Solved!], http://www.perlmonks.org/?node_id=1121101	[reply]

Back to Seekers of Perl Wisdom