Arrays, Strings, and Pattern Techniques · String Algorithms

Rabin-Karp Algorithm

Rabin-Karp introduces rolling hashes for efficient pattern matching across a longer string.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

This is an advanced string topic for students ready to connect hashing with search.

Guided Lesson Notes

Understanding Rabin-Karp Algorithm

Rabin-Karp Algorithm focuses on contiguous sequences, index movement, and the state that can be reused while scanning. Rabin-Karp introduces rolling hashes for efficient pattern matching across a longer string.

The mental model is this: picture the input as boxes with numbered positions; every algorithm decision should say which positions are being read, updated, skipped, or remembered. That picture matters because it tells the student what information is available immediately and what must be searched, stored, or recomputed.

The core invariant is that the variables beside the array must summarize exactly the part of the array that has already been processed. If a solution cannot state that rule, the code may still run on a sample input but fail on edge cases.

A strong implementation usually uses careful loops, boundary checks, and small helper variables for sums, counts, positions, or best answers. The goal is not just to memorize an API; the goal is to know why each operation is allowed and what it costs.

In competitive programming, Rabin-Karp Algorithm tends to appear when the problem asks about a subarray, substring, range, pair, frequency, or a condition over consecutive values. Spotting that signal is often the difference between a nested-loop solution and an efficient one.

Visual Model

A small picture for Rabin-Karp Algorithm

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

Array and string techniques usually become clear when each index has a job: scan, compare, count, enter a range, leave a range, or store a best answer.

Key Ideas

Pattern matching
Rolling hash updates
Collision checks

Practice Prompts

Trace a rolling hash over a short string.
Compare direct substring checks with hash-assisted matching.

Vocabulary

Terms students should be able to say clearly

Index

The numeric position used to access an item directly.

Window

A contiguous section of the array or string currently being considered.

Prefix

Information accumulated from the start of the sequence up to a position.

Boundary

The first or last valid position included in the current scan.

State

The running information kept while the loop moves.

Invariant

The rule that makes the running state trustworthy after each iteration.

Worked Example

Worked example: tracing Rabin-Karp Algorithm

Use a tiny input and focus on pattern matching. The goal is to see how the topic changes state before scaling it to a full problem.

1Write a small input where Rabin-Karp Algorithm is clearly useful.
2Label the part of the input related to Pattern matching.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Indexed access	O(1)	Direct index lookup is fast when the position is known.
Full scan	O(n)	Most search, count, and validation tasks inspect each item once.
Middle insert/delete	O(n)	Items often need to shift to keep order.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Rabin-Karp Algorithm interview problem: Find All Anagram Starts

Interview medium

Problem

Given a text string and a pattern string, print every 0-based index where an anagram of the pattern starts in the text.

Input

The first line contains text. The second line contains pattern. Both use lowercase letters.

Output

Print all starting indices separated by spaces, or NONE if no anagram appears.

Sample Input

cbaebabacd
abc

Sample Output

0 6

Why the sample works

The substrings cba and bac are anagrams of abc.

Approach

1Track frequency counts for the pattern and the current window.
2Slide a fixed-size window across the text.
3After adding the right character and removing the left overflow, compare counts.
4Every equal frequency vector marks an anagram start.

O(26n) time and O(1) extra space.

Java Solution

import java.util.*;

public class Main {
  static boolean same(int[] a, int[] b) {
    for (int i = 0; i < 26; i++) {
      if (a[i] != b[i]) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String text = sc.nextLine().trim();
    String pattern = sc.nextLine().trim();

    int[] need = new int[26];
    int[] window = new int[26];
    for (char ch : pattern.toCharArray()) need[ch - 'a']++;

    List<Integer> answer = new ArrayList<>();
    int size = pattern.length();

    for (int right = 0; right < text.length(); right++) {
      window[text.charAt(right) - 'a']++;
      if (right >= size) {
        window[text.charAt(right - size) - 'a']--;
      }
      if (right >= size - 1 && same(need, window)) {
        answer.add(right - size + 1);
      }
    }

    if (answer.isEmpty()) {
      System.out.println("NONE");
    } else {
      for (int i = 0; i < answer.size(); i++) {
        if (i > 0) System.out.print(" ");
        System.out.print(answer.get(i));
      }
      System.out.println();
    }
  }
}

Python Solution

text = input().strip()
pattern = input().strip()

need = [0] * 26
window = [0] * 26
for ch in pattern:
    need[ord(ch) - ord('a')] += 1

answer = []
size = len(pattern)

for right, ch in enumerate(text):
    window[ord(ch) - ord('a')] += 1
    if right >= size:
        window[ord(text[right - size]) - ord('a')] -= 1
    if right >= size - 1 and window == need:
        answer.append(right - size + 1)

if answer:
    print(*answer)
else:
    print("NONE")

Practice Challenge

Make the idea your own

Create a two-minute explanation of Rabin-Karp Algorithm: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free Consultation Text Us Open Online Compiler