This algorithm is based on the concept of hashing.

This algorithm was authored by Rabin and Karp in 1987.

Problem: Given two strings — a pattern ss and a text tt, determine if the pattern appears in the text and if it does, enumerate all its occurrences in O(|s|+|t|)O(|s|+|t|) time.

Algorithm: Calculate the hash for the pattern ss. Calculate hash values for all the prefixes of the text tt. Now, we can compare a substring of length |s||s| with ss in constant time using the calculated hashes. So, compare each substring of length |s||s| with the pattern. This will take a total of O(|t|)O(|t|) time. Hence the final complexity of the algorithm is O(|t|+|s|)O(|t|+|s|): O(|s|)O(|s|) is required for calculating the hash of the pattern and O(|t|)O(|t|) for comparing each substring of length |s||s| with the pattern.


The rank of a matrix is the largest number of linearly independent rows/columns of the matrix. The rank is not only defined for square matrices.

The rank of a matrix can also be defined as the largest order of any non-zero minor in the matrix.

Let the matrix be rectangular…

You are given a directed graph with nn vertices and mm edges. You have to number the vertices so that every edge leads from the vertex with a smaller number assigned to the vertex with a larger one.

In other words, you want to find a permutation of the vertices…

Well, you might have faced this problem in your coding life. Also you might know the answer already. The problem was about the std::map or say std::multimap, both of them are special type of containers who can sort the items by a comparing function pointer(or a built-in one like std::less)…

We are given a function f(x)f(x) which is unimodal on an interval [l,r][l,r]. By unimodal function, we mean one of two behaviors of the function:

  1. The function strictly increases first, reaches a maximum (at a single point or over an interval), and then strictly decreases.
  2. The function strictly decreases first…


Some dynamic programming problems have a recurrence of this form:


Where C(k,j)C(k,j) is a cost function and dp(i,j)=0dp(i,j)=0 when j<0j<0.

Say 0≤i<m0≤i<m and 0≤j<n0≤j<n, and evaluating CC takes O(1)O(1) time. Then the straightforward evaluation of the above recurrence is O(mn2)O(mn2). …

You are given a directed or undirected weighted graph with nn vertices and mm edges. The weights of all edges are non-negative. You are also given a starting vertex ss. …

Data Abstraction

Data Abstraction refers to the process of hiding irrelevant details from the user. So, what is the meaning of irrelevant details? Let’s understand this with one example. Example: If we want to access any mail from our Gmail then we don’t know where that data is physically stored i.e is…

Rajput Ankit

Power corrupts; absolute power corrupts absolutely.

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