String Matching Algorithms

Problem Statement

Given a search string N='ABCDEFGHIJKLMNOPQRSTUVWXYZ' and a pattern M='DEF' , we want to see if the pattern M can be found in the string N.

Naive Approach

The Naive implementation of the search algorithm will compare the pattern M against all possible substrings of that length in the search string N.

Rabin-Karp Approach

Overview

The Rabin-Karp Algorithm reduces the worst-case time complexity for string matching by using a hash function to perform an approximate check for each positions. Only if an approximate check is found, then an exact comparison can be done.

Example

As an example, given the string: LEETCODE and a substring TCO, the Rabin-Karp Algorithm will perform the following computations.

  1. hash(“LEE”)=“a1”. Don’t need to perform a full check of the substrings.
  2. hash(“EET”)=“a2”. No Check needed.
  3. hash(“ETC”)=“a3”. No Check needed.
  4. hash(“TCO”)=X. The result of the hash of this substring to the pattern is equivalent. Compare in linear time O(M) these two strings for a match. Yes, there is a match found.
  5. hash(“COD”)=“a4”. No Check needed.
  6. hash(“ODE”)=“a5”. No Check needed.

Analysis & Considerations

The Rabin-Karp Algorithm uses the notion of hashing to reduce the complete search space by removing the need for performing full substring comparisons on every possible substring.

  1. Hashing — This algorithm introduces the need to hash the pattern string as well as every substring of that length. If the hashing algorithm performs this work in O(M) time, then the resulting algorithm will run in O(M*N) time. The solution to this is using a Rolling Hash algorithm, which computes in constant time a given hash as the algorithm rolls through the search string.
  1. Hash

Applications

KMP Approach

Reduces worst-case time for string matching by extracting more information from each mismatch, allowing them to skip over positions of the text that are guaranteed not to match.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store