# 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

# 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.

--

--