AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content

12 String algorithms: KMP, Z and hashing / Checkpoint

Checkpoint — String algorithms

60 min · +25 XP · 1 exercise · 10 questions

Exercise0/1
Quiz · 70% to clear10 q

A timed checkpoint on the module: building and using the prefix function, KMP matching, the Z-function's box, rolling hashes and their collisions, and borders and periods.

How it works. Sixty minutes from the moment you start the timer: ten questions and one program. 70% on the questions and the program accepted clears the module.

Before you start, make sure you can answer these from memory:

  • The prefix function of aabaaab, and what pi[n − 1] means.
  • Where j falls back to after a full match in KMP, and why the text index never moves back.
  • What the Z-function's box [l, r) lets you skip.
  • How to read the hash of s[l..r) from prefix hashes, and why one modulus is not enough.

The program prints a string's longest border, its smallest period and how many times that period repeats.

Common questions

How do you find the smallest period of a string with KMP?

Compute the prefix function and take b = pi[n − 1], the longest border. The smallest period is p = n − b: shifting the string by p lines every character up with an equal one. The string is a whole number of copies of its first p characters exactly when p divides n.

Why use two moduli for string hashing?

With one modulus near 10^9, two different strings collide with probability about 1/p each, and among 10^5 substrings the birthday bound makes some collision likely; fixed bases can also be attacked by crafted tests. Two independent moduli multiply the probabilities, around 10^-18 per pair.

AI InterviewGet started

KMP and String Hashing Quiz: Prefix Function Practice Test

A timed practice test on string algorithms in C++: the KMP prefix function, the Z-function, rolling hashes and collisions, and a border-and-period program.

Checkpoint — String algorithms is the checkpoint that closes the String algorithms: KMP, Z and hashing module: a graded quiz and whole-program exercises, passed at 70%.

Instructions

A timed checkpoint on the module: building and using the prefix function, KMP matching, the Z-function's box, rolling hashes and their collisions, and borders and periods.

How it works. Sixty minutes from the moment you start the timer: ten questions and one program. 70% on the questions and the program accepted clears the module.

Before you start, make sure you can answer these from memory:

  • The prefix function of aabaaab, and what pi[n − 1] means.
  • Where j falls back to after a full match in KMP, and why the text index never moves back.
  • What the Z-function's box [l, r) lets you skip.
  • How to read the hash of s[l..r) from prefix hashes, and why one modulus is not enough.

The program prints a string's longest border, its smallest period and how many times that period repeats.

Common questions

How do you find the smallest period of a string with KMP?

Compute the prefix function and take b = pi[n − 1], the longest border. The smallest period is p = n − b: shifting the string by p lines every character up with an equal one. The string is a whole number of copies of its first p characters exactly when p divides n.

Why use two moduli for string hashing?

With one modulus near 10^9, two different strings collide with probability about 1/p each, and among 10^5 substrings the birthday bound makes some collision likely; fixed bases can also be attacked by crafted tests. Two independent moduli multiply the probabilities, around 10^-18 per pair.

Exercise

Border, period and repeats

Read a string s of lowercase letters (length n). Print one line:

border=<b> period=<p> repeats=<r>

  • b — the length of the longest proper prefix of s that is also its suffix;
  • p = n − b — the smallest period (s[i] = s[i + p] for every valid i);
  • r = n / p when p divides n (then s is r copies of its first p letters), otherwise 1.

Use the prefix function: b = pi[n − 1]. O(n).

Constraints: 1 ≤ n ≤ 10^6.

abcabcabc

prints border=6 period=3 repeats=3; aabaa prints border=2 period=3 repeats=1.

In this module: String algorithms: KMP, Z and hashing

← KMP, the Z-function and rolling hashes