Strings, bits, and mathematics.

Linear string algorithms avoid restarting comparisons after a mismatch. They preserve what the matched prefix already proves. Number-theory tools apply the same idea algebraically: binary exponentiation reuses powers, a smallest-prime-factor sieve reuses earlier divisibility work, and factorial tables turn repeated combinations into constant-time queries.

KMP prefix function

prefix[i] is the length of the longest proper prefix of text[0..i] that is also its suffix. On mismatch after matching length characters, the only remaining candidate borders are borders of that matched prefix. Following prefix[length - 1] skips comparisons already known to fail.

prefix_function.cppstd::vector<std::size_t> prefix_function(std::string_view text) {
    std::vector<std::size_t> prefix(text.size(), 0);
    for (std::size_t i = 1; i < text.size(); ++i) {
        std::size_t length = prefix[i - 1];
        while (length > 0 && text[i] != text[length])
            length = prefix[length - 1];
        if (text[i] == text[length]) ++length;
        prefix[i] = length;
    }
    return prefix;
}

Pattern search can build pattern + separator + text and report positions whose prefix value equals the pattern length. The separator must not occur in either input. A streaming KMP matcher avoids that precondition and avoids allocating the combined string.

find_all_kmp.cppstd::vector<std::size_t> find_all_kmp(
    std::string_view pattern,
    std::string_view text
) {
    std::string joined(pattern);
    joined.push_back('\0'); // precondition: inputs contain no NUL byte
    joined.append(text);
    const auto prefix = prefix_function(joined);

    std::vector<std::size_t> matches;
    for (std::size_t i = pattern.size() + 1; i < joined.size(); ++i)
        if (prefix[i] == pattern.size())
            matches.push_back(i - 2 * pattern.size());
    return matches;
}

For a string of length n, let period = n - prefix[n - 1]. It is a repeating period exactly when n % period == 0. Follow prefix[n-1], then its own prefix link, to enumerate all borders. Propagating occurrence counts backward along those links counts every prefix occurrence in linear time.

Z function

z[i] is the length of the common prefix between the whole string and the suffix beginning at i. Maintain the rightmost known matching interval [left, right). Positions inside it can reuse a previously computed Z value, capped by the interval boundary.

z_function.cppstd::vector<std::size_t> z_function(std::string_view text) {
    std::vector<std::size_t> z(text.size(), 0);
    if (text.empty()) return z;
    z[0] = text.size();

    std::size_t left = 0, right = 0;
    for (std::size_t i = 1; i < text.size(); ++i) {
        if (i < right) z[i] = std::min(right - i, z[i - left]);
        while (i + z[i] < text.size() &&
               text[z[i]] == text[i + z[i]])
            ++z[i];
        if (i + z[i] > right) {
            left = i;
            right = i + z[i];
        }
    }
    return z;
}

KMP and Z both perform exact matching in linear time. Use KMP when border fallback and periods are central. Use Z when the desired output is explicitly a prefix-match length at every position. Either can search by prepending the pattern and a separator.

Double rolling hash

A polynomial prefix hash supports a half-open substring hash in constant time. Subtract the prefix contribution multiplied by the appropriate base power. C++ remainder keeps the sign of the dividend, so normalize a negative result. Two independent moduli reduce collision probability. equality is still probabilistic unless matching substrings are verified directly.

double_rolling_hash.cppstd::pair<std::int64_t, std::int64_t>
slice(std::size_t begin, std::size_t end) const {
    const std::size_t length = end - begin;
    auto first = (
        first_[end] - first_[begin] * first_power_[length]
    ) % first_modulus;
    auto second = (
        second_[end] - second_[begin] * second_power_[length]
    ) % second_modulus;
    if (first < 0) first += first_modulus;
    if (second < 0) second += second_modulus;
    return {first, second};
}

With moduli near 10⁹, multiplying two residues fits in signed 64 bits because the product remains below roughly 10¹⁸. Larger moduli require unsigned __int128 or a specialized multiplication method. Adversarial inputs can target fixed bases, so randomizing the base at process start is appropriate where inputs are untrusted.

Manacher’s palindrome radii

Maintain the rightmost palindrome. A center inside it mirrors another center across the current midpoint, so the new radius starts at the smaller of the mirror radius and the distance to the right boundary. Expand only beyond the portion already proved. Separate arrays for odd and even centers avoid sentinel-character preconditions.

manacher_odd.cppstd::vector<std::size_t> odd_radius(std::string_view text) {
    const auto size = static_cast<std::ptrdiff_t>(text.size());
    std::vector<std::size_t> radius(text.size(), 0);
    std::ptrdiff_t left = 0, right = -1;

    for (std::ptrdiff_t center = 0; center < size; ++center) {
        std::ptrdiff_t r = center > right
            ? 1
            : std::min<std::ptrdiff_t>(
                  static_cast<std::ptrdiff_t>(
                      radius[static_cast<std::size_t>(left + right - center)]
                  ),
                  right - center + 1
              );
        while (center - r >= 0 && center + r < size &&
               text[static_cast<std::size_t>(center - r)] ==
                   text[static_cast<std::size_t>(center + r)])
            ++r;
        radius[static_cast<std::size_t>(center)] =
            static_cast<std::size_t>(r);
        if (center + r - 1 > right) {
            left = center - r + 1;
            right = center + r - 1;
        }
    }
    return radius;
}

The odd palindrome length at center i is 2*radius[i] - 1. Even radii use the gap before i as a center and begin with zero rather than one. For only the longest palindrome, expand-around-center is O(n²) worst case but much shorter. Palindrome DP is preferable when later transitions need an is_palindrome[l][r] table.

Bit manipulation

XOR is associative and commutative. x ^ x == 0 and x ^ 0 == x. Therefore paired values cancel regardless of order.

single_number.cppint single_number(std::span<const int> values) {
    int answer = 0;
    for (const int value : values) answer ^= value;
    return answer;
}

Use unsigned types for shifts. Shifting a negative signed value, shifting into an unrepresentable signed result, or shifting by the type width or more is invalid. For “two unique numbers, all others paired,” XOR all values, isolate one differing bit, then XOR values in the two bit groups separately.

Modular arithmetic

Binary exponentiation maintains result * base^exponent equivalent to the original power modulo m. If the current exponent bit is one, move one base factor into the result. Square the base and halve the exponent each iteration.

modular_power.cppstd::int64_t modular_power(
    std::int64_t base,
    std::int64_t exponent,
    std::int64_t modulus
) {
    std::int64_t result = 1 % modulus;
    base %= modulus;
    if (base < 0) base += modulus;

    while (exponent > 0) {
        if (exponent & 1) result = result * base % modulus;
        base = base * base % modulus;
        exponent >>= 1;
    }
    return result;
}

If p is prime and a is not divisible by p, Fermat’s theorem gives a^(p-2) mod p as the multiplicative inverse. A composite modulus requires extended Euclid, and an inverse exists only when gcd(a, m) == 1. Normalize subtraction with (value % mod + mod) % mod or one conditional addition when the value lies in (-mod, mod).

Sieve and factorization

A smallest-prime-factor table costs the same asymptotic memory as a boolean prime table but also factors every number up to the limit by repeatedly dividing by its recorded factor.

smallest_prime_factors.cppstd::vector<int> smallest_prime_factors(int limit) {
    std::vector<int> factor(
        static_cast<std::size_t>(limit + 1),
        0
    );
    for (int prime = 2; prime <= limit; ++prime) {
        if (factor[static_cast<std::size_t>(prime)] != 0) continue;
        for (int multiple = prime; multiple <= limit; multiple += prime) {
            auto& entry = factor[static_cast<std::size_t>(multiple)];
            if (entry == 0) entry = prime;
        }
    }
    return factor;
}

For only primality, begin marking at prime * prime because smaller multiples already have a smaller factor. Widen that product before computing it. Trial division for one number stops when divisor > x / divisor, avoiding overflow in divisor * divisor. A leftover x greater than one is prime.

Combinations modulo a prime

Precompute factorials and inverse factorials once. Computing the final inverse factorial with one modular inverse and walking backward turns n exponentiations into one.

combinations_mod_prime.cppfact.resize(limit + 1);
inverse_fact.resize(limit + 1);
fact[0] = 1;
for (std::size_t i = 1; i <= limit; ++i)
    fact[i] = fact[i - 1] * static_cast<long long>(i) % modulus;

inverse_fact[limit] = modular_power(fact[limit], modulus - 2, modulus);
for (std::size_t i = limit; i > 0; --i)
    inverse_fact[i - 1] =
        inverse_fact[i] * static_cast<long long>(i) % modulus;

auto choose = [&](std::size_t n, std::size_t r) -> long long {
    if (r > n) return 0;
    return fact[n] * inverse_fact[r] % modulus *
           inverse_fact[n - r] % modulus;
};

The factorial method assumes n is below the prime modulus. Lucas’s theorem handles large n digit by digit in base p. Composite moduli need prime-power factorization and the Chinese remainder theorem rather than Fermat inverses.

String and math decision table