String Matching Algorithms

Problem Statement

Naive Approach

Rabin-Karp Approach

Overview

Example

  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

  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

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Java Log file tailer (tail -f) in Spring Boot

Configuring Argo CD on a multi-node Hetzner Cloud

Go 1.16 Embed and FS

POSIX Timer

Connectivity Wrapper: Network-Aware Flutter App

Connectivity Wrapper

Hi Quackers!

Tips for Loading Dataset and Importing Libraries in Python

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
Adam Garcia

Adam Garcia

More from Medium

Airflow failed to login:

Beginning today with Apache Kafka and Confluent 100 Days.

How To Pin Files Directly To Pinata In React

Antenna toolbox: Radiation pattern for linear array yields