# Rabin-Karp Algorithm for string matching

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.

# Finding the rank of a matrix

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…

# Topological Sorting

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…

# Dynamically sorting both keys and values

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)…

# Ternary Search

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…

# Preconditions

Some dynamic programming problems have a recurrence of this form:

dp(i,j)=min0≤k≤j{dp(i−1,k−1)+C(k,j)}dp(i,j)=min0≤k≤j{dp(i−1,k−1)+C(k,j)}

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). …

# Dijkstra Algorithm

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.