AlgoScope

String Matching

Looking for a word in a text is sliding the word along and checking whether it fits. The naive way tries every position and re-reads characters after each failure. KMP first studies the pattern: for every prefix it records the longest border, a proper prefix that is also a suffix, so after a mismatch it knows how far the pattern can jump without missing a match and never re-reads the text. Rabin-Karp takes a different shortcut: it compares numbers instead of strings, a rolling hash of each window against the hash of the pattern, and only reads characters when the numbers agree. Manacher's algorithm answers a different question with the same machinery: the longest palindrome. Putting a separator in every gap makes even and odd palindromes one case, and a box around the palindrome that reaches furthest right lets most positions copy their radius from a mirror instead of comparing from scratch, which is what turns the obvious quadratic expansion into linear time.

The player

Manacher over 17 transformed positions.012345678910111213141516tr#a#b#a#c#a#b#a#d#0

Find the longest palindrome in "abacabad". A palindrome can have an even or an odd length, and that is two cases nobody wants to write twice, so put a # in every gap and at both ends: "#a#b#a#c#a#b#a#d#". Every palindrome in there is now odd, centred on one position, and its radius is exactly the length of the palindrome in the original text.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.

  1. What radius does position 4 start from, before any comparing?

    • 0
    • 2

    Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 2) = 0. Copying more than the box reaches would assume characters nobody has looked at.

  2. What radius does position 5 start from, before any comparing?

    • 0
    • 1

    Answer: 1. Inside the box the answer is min(mirror radius, distance to the right edge): min(1, 1) = 1. Copying more than the box reaches would assume characters nobody has looked at.

  3. What radius does position 8 start from, before any comparing?

    • 0
    • 6

    Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 6) = 0. Copying more than the box reaches would assume characters nobody has looked at.

  4. What radius does position 9 start from, before any comparing?

    • 0
    • 1
    • 5

    Answer: 1. Inside the box the answer is min(mirror radius, distance to the right edge): min(1, 5) = 1. Copying more than the box reaches would assume characters nobody has looked at.

  5. What radius does position 10 start from, before any comparing?

    • 0
    • 4

    Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 4) = 0. Copying more than the box reaches would assume characters nobody has looked at.

  6. What radius does position 11 start from, before any comparing?

    • 0
    • 3

    Answer: 3. Inside the box the answer is min(mirror radius, distance to the right edge): min(3, 3) = 3. Copying more than the box reaches would assume characters nobody has looked at.

  7. What radius does position 12 start from, before any comparing?

    • 0
    • 2

    Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 2) = 0. Copying more than the box reaches would assume characters nobody has looked at.

  8. What radius does position 13 start from, before any comparing?

    • 0
    • 1

    Answer: 1. Inside the box the answer is min(mirror radius, distance to the right edge): min(1, 1) = 1. Copying more than the box reaches would assume characters nobody has looked at.

How it runs, step by step

  1. Find the longest palindrome in "abacabad". A palindrome can have an even or an odd length, and that is two cases nobody wants to write twice, so put a # in every gap and at both ends: "#a#b#a#c#a#b#a#d#". Every palindrome in there is now odd, centred on one position, and its radius is exactly the length of the palindrome in the original text.

    Manacher over 17 transformed positions.

  2. Position 1 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.

    Position 1 is outside the box. Starting radius 0.

  3. Each comparison one step further out matches, 1 time, so the radius at 1 grows to 1, which is the palindrome "a" in the original text. It reaches further right than the old box, so the box moves to centre 1, right edge 2.

    Radius at 1 is 1.

  4. Position 2 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.

    Position 2 is outside the box. Starting radius 0.

  5. Comparing the characters one step out fails immediately, so the radius at 2 stays 0.. The box is unchanged.

    Radius at 2 is 0.

  6. Position 3 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.

    Position 3 is outside the box. Starting radius 0.

  7. Each comparison one step further out matches, 3 times, so the radius at 3 grows to 3, which is the palindrome "aba" in the original text. It reaches further right than the old box, so the box moves to centre 3, right edge 6.

    Radius at 3 is 3.

  8. Position 4 sits inside the palindrome centred at 3, which reaches index 6. Its mirror image about 3 is position 2, with radius 0. The mirror can be copied, but only as far as the box reaches: 2. So the starting radius is the smaller of the two, 0.

    Position 4 mirrors 2. Starting radius 0.

  9. Comparing the characters one step out fails immediately, so the radius at 4 stays 0.. The box is unchanged.

    Radius at 4 is 0.

  10. Position 5 sits inside the palindrome centred at 3, which reaches index 6. Its mirror image about 3 is position 1, with radius 1. The mirror can be copied, but only as far as the box reaches: 1. So the starting radius is the smaller of the two, 1.

    Position 5 mirrors 1. Starting radius 1.

  11. Comparing the characters one step out fails immediately, so the radius at 5 stays 1., which is the palindrome "a" in the original text. The box is unchanged.

    Radius at 5 is 1.

  12. Position 6 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.

    Position 6 is outside the box. Starting radius 0.

  13. Comparing the characters one step out fails immediately, so the radius at 6 stays 0.. The box is unchanged.

    Radius at 6 is 0.

  14. Position 7 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.

    Position 7 is outside the box. Starting radius 0.

  15. Each comparison one step further out matches, 7 times, so the radius at 7 grows to 7, which is the palindrome "abacaba" in the original text. It reaches further right than the old box, so the box moves to centre 7, right edge 14.

    Radius at 7 is 7.

  16. Position 8 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 6, with radius 0. The mirror can be copied, but only as far as the box reaches: 6. So the starting radius is the smaller of the two, 0.

    Position 8 mirrors 6. Starting radius 0.

  17. Comparing the characters one step out fails immediately, so the radius at 8 stays 0.. The box is unchanged.

    Radius at 8 is 0.

  18. Position 9 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 5, with radius 1. The mirror can be copied, but only as far as the box reaches: 5. So the starting radius is the smaller of the two, 1.

    Position 9 mirrors 5. Starting radius 1.

  19. Comparing the characters one step out fails immediately, so the radius at 9 stays 1., which is the palindrome "a" in the original text. The box is unchanged.

    Radius at 9 is 1.

  20. Position 10 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 4, with radius 0. The mirror can be copied, but only as far as the box reaches: 4. So the starting radius is the smaller of the two, 0.

    Position 10 mirrors 4. Starting radius 0.

  21. Comparing the characters one step out fails immediately, so the radius at 10 stays 0.. The box is unchanged.

    Radius at 10 is 0.

  22. Position 11 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 3, with radius 3. The mirror can be copied, but only as far as the box reaches: 3. So the starting radius is the smaller of the two, 3.

    Position 11 mirrors 3. Starting radius 3.

  23. Comparing the characters one step out fails immediately, so the radius at 11 stays 3., which is the palindrome "aba" in the original text. The box is unchanged.

    Radius at 11 is 3.

  24. Position 12 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 2, with radius 0. The mirror can be copied, but only as far as the box reaches: 2. So the starting radius is the smaller of the two, 0.

    Position 12 mirrors 2. Starting radius 0.

  25. Comparing the characters one step out fails immediately, so the radius at 12 stays 0.. The box is unchanged.

    Radius at 12 is 0.

  26. Position 13 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 1, with radius 1. The mirror can be copied, but only as far as the box reaches: 1. So the starting radius is the smaller of the two, 1.

    Position 13 mirrors 1. Starting radius 1.

  27. Comparing the characters one step out fails immediately, so the radius at 13 stays 1., which is the palindrome "a" in the original text. The box is unchanged.

    Radius at 13 is 1.

  28. Position 14 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.

    Position 14 is outside the box. Starting radius 0.

  29. Comparing the characters one step out fails immediately, so the radius at 14 stays 0.. The box is unchanged.

    Radius at 14 is 0.

  30. Position 15 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.

    Position 15 is outside the box. Starting radius 0.

  31. Each comparison one step further out matches, 1 time, so the radius at 15 grows to 1, which is the palindrome "d" in the original text. It reaches further right than the old box, so the box moves to centre 15, right edge 16.

    Radius at 15 is 1.

  32. The largest radius is 7 at position 7, which is the palindrome "abacaba" starting at index 0 of the original text. Every position was visited once and the right edge of the box only ever moves forward, so the 27 character comparisons are O(n) in total: the mirror is what turns the obvious O(n^2) expansion into linear time.

    The longest palindrome is abacaba, length 7.

The code

String Matching, in Python

def naive(text, pattern):
    found = []
    for shift in range(len(text) - len(pattern) + 1):
        j = 0
        while j < len(pattern) and text[shift + j] == pattern[j]:  # compare left to right
            j += 1
        if j == len(pattern):                                      # whole pattern matched
            found.append(shift)
    return found

def prefix_function(p):
    pi = [0] * len(p)
    for i in range(1, len(p)):
        k = pi[i - 1]                                              # longest border so far
        while k > 0 and p[i] != p[k]:                              # fall back to a shorter border
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp(text, pattern):
    pi = prefix_function(pattern)
    found = []
    j = 0                                                          # matched pattern chars
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:                     # slide, keep the border
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            found.append(i - j + 1)
            j = pi[j - 1]
    return found

def rabin_karp(text, pattern, base=31, mod=101):
    m = len(pattern)
    target = 0
    for c in pattern:
        target = (target * base + ord(c)) % mod
    hash = 0
    for c in text[:m]:
        hash = (hash * base + ord(c)) % mod
    found = []
    for shift in range(len(text) - m + 1):
        if hash == target and text[shift:shift + m] == pattern:    # verify
            found.append(shift)
        if shift + m < len(text):
            hash = roll(hash, text[shift], text[shift + m])        # O(1)
    return found

def boyer_moore(text, pattern):                                    # bad character rule only
    last = {}
    for i, c in enumerate(pattern):                                # rightmost index
        last[c] = i
    found = []
    shift = 0
    while shift <= len(text) - len(pattern):
        j = len(pattern) - 1
        while j >= 0 and text[shift + j] == pattern[j]:            # compare right to left
            j -= 1
        if j < 0:
            found.append(shift)
            shift += 1
        else:
            shift += max(1, j - last.get(text[shift + j], -1))     # line the bad char up with its last copy
    return found

def z_array(s):                                                    # z[i]: longest match of s[i..] with a prefix
    z = [0] * len(s)
    l = r = 0                                                      # [l, r]: rightmost match box so far
    for i in range(1, len(s)):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])                        # inside the box: copy from the mirror
        while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:        # then extend by comparing
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z
# matching: z of pattern + "$" + text; z[i] == m marks a match at i - m - 1

def manacher(s):
    t = "#" + "#".join(s) + "#"                                    # odd length: every centre is a character
    p = [0] * len(t)
    c = r = 0                                                      # [c - r, c + r]: rightmost palindrome
    for i in range(1, len(t) - 1):
        if i < r:
            p[i] = min(r - i, p[2 * c - i])                        # inside: copy the mirror, capped by r
        while (i - p[i] - 1 >= 0 and i + p[i] + 1 < len(t) and
               t[i + p[i] + 1] == t[i - p[i] - 1]):                # then extend one pair at a time
            p[i] += 1
        if i + p[i] > r:                                           # a palindrome reaching further: new box
            c, r = i, i + p[i]
    k = max(range(len(p)), key=lambda i: p[i])                     # radius in t is length in s
    return s[(k - p[k]) // 2:(k + p[k]) // 2]

String Matching, in JavaScript

function naive(text, pattern) {
  const found = [];
  for (let shift = 0; shift <= text.length - pattern.length; shift++) {
    let j = 0;
    while (j < pattern.length && text[shift + j] === pattern[j]) j++;    // compare left to right
    if (j === pattern.length) found.push(shift);                         // whole pattern matched
  }
  return found;
}

function prefixFunction(p) {
  const pi = new Array(p.length).fill(0);
  for (let i = 1; i < p.length; i++) {
    let k = pi[i - 1];                                                   // longest border so far
    while (k > 0 && p[i] !== p[k]) k = pi[k - 1];                        // fall back to a shorter border
    if (p[i] === p[k]) k++;
    pi[i] = k;
  }
  return pi;
}

function kmp(text, pattern) {
  const pi = prefixFunction(pattern);
  const found = [];
  let j = 0;                                                             // matched pattern chars
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = pi[j - 1];               // slide, keep the border
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) { found.push(i - j + 1); j = pi[j - 1]; }
  }
  return found;
}

function rabinKarp(text, pattern, base = 31, mod = 101) {
  const m = pattern.length;
  const target = [...pattern].reduce((h, c) => (h * base + c.charCodeAt(0)) % mod, 0);
  let hash = [...text.slice(0, m)].reduce((h, c) => (h * base + c.charCodeAt(0)) % mod, 0);
  const found = [];
  for (let shift = 0; shift <= text.length - m; shift++) {
    if (hash === target && text.slice(shift, shift + m) === pattern) found.push(shift);   // verify
    if (shift + m < text.length) hash = roll(hash, text[shift], text[shift + m]);         // O(1)
  }
  return found;
}

function boyerMoore(text, pattern) {                                     // bad character rule only
  const last = new Map(); [...pattern].forEach((c, i) => last.set(c, i));   // rightmost index
  const found = [];
  let shift = 0;
  while (shift <= text.length - pattern.length) {
    let j = pattern.length - 1;
    while (j >= 0 && text[shift + j] === pattern[j]) j--;                // compare right to left
    if (j < 0) { found.push(shift); shift += 1; }
    else shift += Math.max(1, j - (last.get(text[shift + j]) ?? -1));    // line the bad char up with its last copy
  }
  return found;
}

function zArray(s) {                                                     // z[i]: longest match of s[i..] with a prefix
  const z = new Array(s.length).fill(0); let l = 0, r = 0;               // [l, r]: rightmost match box so far
  for (let i = 1; i < s.length; i++) {
    if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);                    // inside the box: copy from the mirror
    while (i + z[i] < s.length && s[z[i]] === s[i + z[i]]) z[i]++;       // then extend by comparing
    if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
  }
  return z;
}                        // matching: z of pattern + "$" + text; z[i] === m marks a match at i - m - 1

function manacher(s) {
  const t = "#" + [...s].join("#") + "#";                                // odd length: every centre is a character
  const p = new Array(t.length).fill(0); let c = 0, r = 0;               // [c - r, c + r]: rightmost palindrome
  for (let i = 1; i < t.length - 1; i++) {
    if (i < r) p[i] = Math.min(r - i, p[2 * c - i]);                     // inside: copy the mirror, capped by r
    while (i - p[i] - 1 >= 0 && i + p[i] + 1 < t.length &&
           t[i + p[i] + 1] === t[i - p[i] - 1]) p[i]++;                  // then extend one pair at a time
    if (i + p[i] > r) { c = i; r = i + p[i]; }                           // a palindrome reaching further: new box
  }
  const k = p.reduce((best, v, i) => (v > p[best] ? i : best), 0);       // radius in t is length in s
  return s.slice(Math.floor((k - p[k]) / 2), Math.floor((k + p[k]) / 2));
}

String Matching, in Kotlin

fun naive(text: String, pattern: String): List<Int> {
    val found = mutableListOf<Int>()
    for (shift in 0..text.length - pattern.length) {
        var j = 0
        while (j < pattern.length && text[shift + j] == pattern[j]) j++   // compare left to right
        if (j == pattern.length) found += shift                          // whole pattern matched
    }
    return found
}

fun prefixFunction(p: String): IntArray {
    val pi = IntArray(p.length)
    for (i in 1 until p.length) {
        var k = pi[i - 1]                                              // longest border so far
        while (k > 0 && p[i] != p[k]) k = pi[k - 1]                     // fall back to a shorter border
        if (p[i] == p[k]) k++
        pi[i] = k
    }
    return pi
}

fun kmp(text: String, pattern: String): List<Int> {
    val pi = prefixFunction(pattern)
    val found = mutableListOf<Int>()
    var j = 0                                                          // matched pattern chars
    for (i in text.indices) {
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1]           // slide, keep the border
        if (text[i] == pattern[j]) j++
        if (j == pattern.length) { found += i - j + 1; j = pi[j - 1] }
    }
    return found
}

fun rabinKarp(text: String, pattern: String, base: Int = 31, mod: Int = 101): List<Int> {
    val m = pattern.length
    val target = pattern.fold(0) { h, c -> (h * base + c.code) % mod }
    var hash = text.take(m).fold(0) { h, c -> (h * base + c.code) % mod }
    val found = mutableListOf<Int>()
    for (shift in 0..text.length - m) {
        if (hash == target && text.substring(shift, shift + m) == pattern) found += shift   // verify
        if (shift + m < text.length) hash = roll(hash, text[shift], text[shift + m])   // O(1)
    }
    return found
}

fun boyerMoore(text: String, pattern: String): List<Int> {         // bad character rule only
    val last = HashMap<Char, Int>(); pattern.forEachIndexed { i, c -> last[c] = i }   // rightmost index
    val found = mutableListOf<Int>()
    var shift = 0
    while (shift <= text.length - pattern.length) {
        var j = pattern.length - 1
        while (j >= 0 && text[shift + j] == pattern[j]) j--            // compare right to left
        if (j < 0) { found += shift; shift += 1 }
        else shift += max(1, j - (last[text[shift + j]] ?: -1))       // line the bad char up with its last copy
    }
    return found
}

fun zArray(s: String): IntArray {                                     // z[i]: longest match of s[i..] with a prefix
    val z = IntArray(s.length); var l = 0; var r = 0                  // [l, r]: rightmost match box so far
    for (i in 1 until s.length) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l])                    // inside the box: copy from the mirror
        while (i + z[i] < s.length && s[z[i]] == s[i + z[i]]) z[i]++   // then extend by comparing
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1 }
    }
    return z
}                       // matching: z of pattern + "$" + text; z[i] == m marks a match at i - m - 1

fun manacher(s: String): String {
    val t = "#" + s.toCharArray().joinToString("#") + "#"   // odd length: every centre is a character
    val p = IntArray(t.length); var c = 0; var r = 0             // [c - r, c + r]: rightmost palindrome
    for (i in 1 until t.length - 1) {
        if (i < r) p[i] = min(r - i, p[2 * c - i])               // inside: copy the mirror, capped by r
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < t.length &&
               t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++     // then extend one pair at a time
        if (i + p[i] > r) { c = i; r = i + p[i] }                // a palindrome reaching further: new box
    }
    val k = p.indices.maxBy { p[it] }                            // radius in t is length in s
    return s.substring((k - p[k]) / 2, (k + p[k]) / 2)
}

Write it yourself

Define countOccurrences(text, pattern) and return how many times the pattern occurs, counting overlaps. It runs in your browser against this lesson's own 2 examples.

// Build the table of how far to fall back on a mismatch, so the text pointer never moves backwards.function countOccurrences(text, pattern) { return 0;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Naive matching is O(n x m) because a mismatch throws away characters already read.
    • pi[i] is the longest border of the first i + 1 pattern characters. KMP jumps to pi[j - 1] on a mismatch.
    • Rabin-Karp compares hashes in O(1) per window and verifies only on a hit. Manacher pads the string with separators and copies each radius from its mirror inside the current box.

    Where this is used

    grep and ripgrepDeveloper tools

    A literal search does not have to read every byte. Boyer-Moore compares the pattern right to left and, on a mismatch, slides the pattern so the offending text character lines up with its last occurrence in the pattern, which can skip nearly a whole pattern length at once. GNU grep is built on that skip. ripgrep goes further and scans for the rarest byte of the pattern with memchr, so most of the file is passed over by a vectorised byte scan and only candidate positions are compared in full.

    Intrusion detection signaturesSecurity

    Snort and Suricata check every packet against thousands of byte patterns at line rate, so one search per signature is out of the question. They use Aho-Corasick, which is the prefix function built over a trie of all the patterns at once: a mismatch follows a failure link to the longest pattern prefix still alive, so the packet is read once no matter how many signatures are loaded. Suricata also ships Hyperscan as an alternative matcher for the same reason, trading preprocessing time for a single pass over the payload.

    rsync and deduplicating backupsBackup and sync

    The receiver splits its copy of a file into blocks and sends their checksums. The sender then rolls a checksum across every offset of its own copy, looks each value up, and transmits only the blocks that never matched. That is the Rabin-Karp window, though rsync's weak checksum is an Adler-32 variant rather than a polynomial hash. Backup tools reuse the trick to cut chunks at content-defined boundaries: restic rolls a Rabin fingerprint over a 64 byte window and borg rolls a Buzhash, so inserting a byte near the start of a file shifts one chunk instead of every chunk after it. All of them need the hash to update in O(1) as the window slides, which is the whole point of the rolling form.

    Substring search in standard librariesStandard libraries

    glibc's strstr and memmem use the two-way algorithm of Crochemore and Perrin, which splits the pattern at a critical position and keeps a linear worst case in constant extra space, unlike KMP's table that is as long as the pattern. CPython added the same algorithm in 3.10, and str.find and the in operator fall back to it when a search starts to look quadratic on a long string. A library call cannot afford to allocate on every search or to stall on a hostile string, which is what makes the more intricate preprocessing worth it.

    Why it works this way

    Why does a mismatch jump to pi[j - 1] instead of starting over?

    The first j characters of the pattern have already matched the text, so the only alignments still worth trying are the ones where a prefix of the pattern lands on characters it is known to match: a prefix of the pattern that is also a suffix of those j characters, which is a border. pi[j - 1] is the longest border, so sliding to it is the smallest jump that cannot step over a match, and any smaller jump would need a longer border that pi says does not exist.

    Why is KMP linear when the inner while loop can spin many times?

    Count what happens to j rather than counting loop iterations. Each text character raises j by at most one, so over the whole text j gains at most n. Every turn of the while loop strictly lowers j, and j never drops below zero, so those turns add up to at most n across the entire run. One character can trigger a long chain of fallbacks, but only because earlier characters paid for it.

    In Rabin-Karp, equal hashes are not a match

    The hash comparison is a filter, not an answer: different windows can share a hash, so the substring comparison after a hit is needed for correctness rather than as a safety check. A modulus as small as the 101 used above collides constantly, and every collision costs a full O(m) comparison, which is how the method degrades to O(n x m). Real uses take a large prime modulus and a random base so an adversary cannot craft collisions. One more trap: the rolling step subtracts the outgoing character's contribution and that can go negative under a modulus, so add the modulus back before taking the remainder.

    Manacher: why a separator in every gap, and why the mirror is capped

    A palindrome of even length has no centre character, so without padding you need one pass for odd centres and another for the gaps between characters. Inserting '#' between every pair and at both ends makes every palindrome odd and centred on a real index, and the radius measured there equals the length of the palindrome in the original string. The copied value p[2 * c - i] has to be capped at r - i because the mirror's palindrome may run past the left edge of the current box, and outside the box nothing has been verified yet. The while loop is what extends past the edge, one pair at a time.

    Read more

    Next up

    Stacks for Expressions

    Balanced brackets

    Next lesson: Stacks for Expressions