CODEWITHSUNDEEP
stringalgorithmpattern-matchingstring-matchingknuth-morris-pratt
Anantha Krishnan
Anantha Krishnan

Reputation: 3088

String pattern matching with one or zero mismatch

Given a string and a pattern to be matched, how efficiently can the matches be found having zero or one mismatch.

e.g) 
S = abbbaaabbbabab
P = abab

Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10)

I tried to modify KMP algorithm but I'm not sure about the approach.

Please give me idea to proceed with the problem.

Thanks.

Upvotes: 8

Views: 4729

Answers (4)

Ruslan Mavlyutov
Ruslan Mavlyutov

Reputation: 41

To find all submatches including one mismatch you need 2 z-functions (one for the original P, and another for reversed P). After that buld array of longest prefix submatches for the original and reversed string S. Later you need to reverse the second array. And in the end everything is easy: run through the first array and check if the length of longest prefix is equal to the length of P. If it is, then it is a match without mistakes. If it is shorter, then check the second array at position (i + length(P) - 1). If sum of two values is equal to length(P) - 1, then it is a submatch with one mistake.

Complexity is O(len(P) + len(S))

Upvotes: 2

Boris Strandjev
Boris Strandjev

Reputation: 46943

Ok I found it! I found the best algorithm!

This might sound a bit brave, but as long as the algorithm I am going to propose has both running time O(m + n) and memory consumption O(m + n) and the entry data itself has the same properties the algorithm can be optimized only in constant.

Algorithms used

I am going to use mix-up between KMP and Rabin Karp algorithms for my solution. Rabin Karp uses rolling hashes for comparing substrings of the initial strings. It requires linear in time precomputing that uses linear additional memory, but from then on the comparison between substrings of the two strings is constant O(1) (this is amortized if you handle collisions properly).

What my solution will not do

My solution will not find all the occurrences in the first string that match the second string with at most 1 difference. However, the algorithm can be modified so that for every starting index in the first string if there is such matching at least one of them will be found (this is left to the reader).

Observations

Let m be the length of the second string and n - the length of the first string. I am going to split the task in two parts: if I am aiming to find a matching with at most one difference, I want to find to substrings of the first string: PREF is going to be the substring before the single difference and SUFF the substring after the difference. I want len(PREF) + len(SUFF) + 1 = m, where PREF or SUFF will be artificially shortened if required (when the strings match without difference).

I am going to base my solution on one very important observation: suppose there is a substring of the first string starting at index i with length m that matches the second string with at most one difference. Then if we take PREF as long as possible there will still be solution for SUFF. This is obvious: I am just pushing the difference as much to the end as possible.

The algorithm

And now follows the algorithm itself. Start off with usual KMP. Every time when the extension of the prefix fails and the fail links are to be followed, first check whether if you skip the next letter the remaining suffix will match the remaining of the second string. If so the sought match with at most one character difference is found. If not - we go on with the ordinary KMP making the Rabin Karp check every time a fail link is to be followed.

Let me clarify further the Rabin Karp check with an example. Suppose we are at certain step of the KMP and we have found that first.substring[i, i + k - 1] matches the first k letters of the second string. Suppose also that the letter first[i + k] is different from second[k]. Then you check whether first.substring[i + k + 1, i + m - 1] matches exactly second.substring[k + 1, m - 1] using Rabin Karp. This is exactly the case in which you have extended the starting prefix form index i as much as possible and you try now whether there is a match with at most one difference.

Rabin Karp will be used only when a fail link is followed, which moves the starting index of the prefix with at least one, which means that at most O(n) Rabin Karp calls are used, every one with complexity O(1) for a total of linear complexity.

Upvotes: 5

jogojapan
jogojapan

Reputation: 69977

A comprehensive overview of the various algorithms and how they compare to each other is given by Gonzalo Navarro in his A guided tour to approximate string matching. Pages 80, 81 and 82 show complexity results, including worst and average cases, and space requirements for the various algorithms.

(In the notation used there, n refers to the length of the text you search, m to the length of the pattern, σ to the size of the alphabet, and k to the maximum edit distance, which is 1 in your case.)

Upvotes: 1

tskuzzy
tskuzzy

Reputation: 36476

This is known as the approximate string matching problem. In your particular case, you want a maximum edit distance of 1.

The bitap algorithm is a fairly fast way of solving it.

Upvotes: 2

Related Questions