I want to modify the Naive algorithm to find out if there is any occurrence of the string P in T as a substring with at most one mismatch - where a mismatch is either one of the following: INSERT, DELETE, OR UPDATE. Let jTj = n; jPj = m.

What will be the worst-case complexity in modified version? Can I use memoization to improve the complexity?

  • 1
    $\begingroup$ It seems the problem you're trying to solve is the edit distance problem, can you mention that in your question? Can you describe this 'naive algorithm'? There is a well known dynamic programming algorithm to solve this problem, see here. Do you wish to improve upon that algorithm, or is that already sufficient? $\endgroup$ – Discrete lizard Jan 7 '18 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.