CSES - String Matching

Solution - Knuth-Morris-Prat Algorithm

Define an array $\pi_S$ on some string $S$ such that $\pi_S[i]$ stores the length of the longest nontrivial prefix of the entire string that is equivalent to a suffix ending at position $i$. Formally,

If we are searching for string $P$ inside of string $T$, create a new string $S = P + \# + T$, where $\#$ is any arbitrary character that does not occur in either string. Then, create an array $\pi_S$ using the KMP algorithm. The answer is simply the number of indicies inside of $\pi_S$ that is equal to $|P|$ (the length of $P$).

Copy
#include <bits/stdc++.h>
using namespace std;

namespace str {
/** Computes the Pi array of s. */
vector<int> pi(const string &s) {
	int n = (int)s.size();
	vector<int> pi_s(n);
	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && s[j] != s[i]) { j = pi_s[j - 1]; }

Copy
from typing import List


def pi(s: str) -> List[int]:
	"""Computes the Pi array of s."""
	n = len(s)
	pi_s = [0] * n
	j = 0
	for i in range(1, n):
		while j > 0 and s[j] != s[i]:

Solution - Z-Algorithm

Like the previous solution, we now define an array $z_S$ such that $z_S[i]$ is the length of the longest prefix beginning at index $i$ that is equivalent to a prefix of the entire string. Formally,

As before, for pattern string $P$ and text string $T$, create a new string $S = P + '\#' + T$, and create the array $z_S$ using the z-algorithm. The answer is the number of indices inside of $z_S$ that is equal to $|P|$.

Copy
#include <bits/stdc++.h>
using namespace std;

namespace str {
// Computes the Z-array of s
vector<int> z(const string &s) {
	int n = (int)s.size();
	vector<int> z_S(n);
	for (int i = 1, l = 0, r = 0; i < n; i++) {
		if (i <= r) { z_S[i] = min(z_S[i - l], r - i + 1); }

Solution - Rabin-Karp Algorithm

Precompute the rolling hash of both $P$ and $T$. Each substring of length $|P|$ can be compared for equality in $\mathcal{O}(1)$ time. Since there is a relatively small number of comparisons, using a single set of hash values is fine (although it doesn't hurt to add more!). Using hash base $9973$ and modulo $10^9 + 7$ suffices (see the string hashing module for more details on this choice).

Copy
#include <bits/stdc++.h>
using namespace std;

namespace str {
// Computes the rolling hash of s with power P and modulo M
vector<long long> rhash(const string &s, const long long P, const long long M) {
	int n = (int)s.size();
	vector<long long> rhash_S(n);
	for (int i = 0; i < n; i++) {
		if (i != 0) { rhash_S[i] = rhash_S[i - 1] * P % M; }