820 Advanced

Manacher's Algorithm — Longest Palindromic Substring

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Manacher's Algorithm — Longest Palindromic Substring" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Finding the longest palindromic substring naively requires O(n^2) time by expanding from each center. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Finding the longest palindromic substring naively requires O(n^2) time by expanding from each center. Manacher's algorithm finds all palindromic substrings — both odd and even length — in O(n) time by reusing previously computed palindrome radii. This is the canonical O(n) solution to "find the longest palindrome in a string," a classic interview problem with practical applications in DNA analysis (palindromic sequences indicate restriction enzyme sites), text compression, and symmetry detection. The key insight is that palindromes inside a larger known palindrome have known minimum radii, avoiding redundant character comparisons.

🎯 Learning Outcomes

• Transform the string with sentinel characters (#) to unify odd/even length palindrome handling

• Understand the center/right-boundary invariant: track the palindrome extending furthest right

• Use the mirror property: p[mirror] = p[i] (limited by the right boundary) as a starting point

• Implement the O(n) linear scan with the amortized argument for why each character is visited O(1) times

• Recover substring positions from the transformed string's palindrome radius array

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Manacher's Algorithm in OCaml *)

(* Transform "abc" -> "#a#b#c#" so all palindromes are odd-length *)
let transform (s : string) : string =
  let n = String.length s in
  let buf = Buffer.create (2 * n + 1) in
  Buffer.add_char buf '#';
  String.iter (fun c -> Buffer.add_char buf c; Buffer.add_char buf '#') s;
  Buffer.contents buf

(* Compute palindrome radius array for transformed string t *)
let manacher (t : string) : int array =
  let n = String.length t in
  let p = Array.make n 0 in
  let c = ref 0 and r = ref 0 in
  for i = 0 to n - 1 do
    let mirror = 2 * !c - i in
    if i < !r then
      p.(i) <- min (p.(mirror)) (!r - i);
    (* Attempt to expand *)
    let a = ref (i - (p.(i) + 1))
    and b = ref (i + (p.(i) + 1)) in
    while !a >= 0 && !b < n && t.[!a] = t.[!b] do
      p.(i) <- p.(i) + 1;
      decr a; incr b
    done;
    if i + p.(i) > !r then begin
      c := i;
      r := i + p.(i)
    end
  done;
  p

(* Return the longest palindromic substring of s *)
let longest_palindrome (s : string) : string =
  if String.length s = 0 then ""
  else begin
    let t = transform s in
    let p = manacher t in
    (* Find centre with maximum radius *)
    let best_c = ref 0 and best_r = ref 0 in
    Array.iteri (fun i r ->
      if r > !best_r then begin best_c := i; best_r := r end
    ) p;
    (* Map back to original string *)
    let start = (!best_c - !best_r) / 2 in
    String.sub s start !best_r
  end

let () =
  let tests = [
    ("babad", "bab");
    ("cbbd",  "bb");
    ("racecar", "racecar");
    ("abacaba", "abacaba");
    ("a", "a");
    ("aabbaa", "aabbaa");
  ] in
  List.iter (fun (input, _expected) ->
    let result = longest_palindrome input in
    Printf.printf "longest_palindrome(%S) = %S\n" input result
  ) tests

Key Differences

Aspect	Rust	OCaml
Transformation	`flat_map` + `once`	`Buffer` with character appending
Radius array	`Vec<usize>`	`int array`
Center/right state	Two `usize` variables	`int ref` pair
Result extraction	`p.iter().enumerate().max_by_key()`	`Array.fold_left` for max
Char handling	`chars()` for Unicode	`Uchar` or byte-level
Sentinel choice	`#` (not in typical ASCII text)	Same; often `\000` for bytes

OCaml Approach

OCaml implements the transformation with Buffer, appending '#' between and around each character. The palindrome radius array is Array.make (2*n+1) 0. Center and right boundary are mutable int ref values. OCaml's pattern matching elegantly handles the three cases: mirror palindrome fits entirely within boundary, mirror radius equals boundary distance, or expansion needed. The String.sub at the end extracts the longest palindromic substring from the original coordinates.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Manacher's Algorithm in OCaml *)

(* Transform "abc" -> "#a#b#c#" so all palindromes are odd-length *)
let transform (s : string) : string =
  let n = String.length s in
  let buf = Buffer.create (2 * n + 1) in
  Buffer.add_char buf '#';
  String.iter (fun c -> Buffer.add_char buf c; Buffer.add_char buf '#') s;
  Buffer.contents buf

(* Compute palindrome radius array for transformed string t *)
let manacher (t : string) : int array =
  let n = String.length t in
  let p = Array.make n 0 in
  let c = ref 0 and r = ref 0 in
  for i = 0 to n - 1 do
    let mirror = 2 * !c - i in
    if i < !r then
      p.(i) <- min (p.(mirror)) (!r - i);
    (* Attempt to expand *)
    let a = ref (i - (p.(i) + 1))
    and b = ref (i + (p.(i) + 1)) in
    while !a >= 0 && !b < n && t.[!a] = t.[!b] do
      p.(i) <- p.(i) + 1;
      decr a; incr b
    done;
    if i + p.(i) > !r then begin
      c := i;
      r := i + p.(i)
    end
  done;
  p

(* Return the longest palindromic substring of s *)
let longest_palindrome (s : string) : string =
  if String.length s = 0 then ""
  else begin
    let t = transform s in
    let p = manacher t in
    (* Find centre with maximum radius *)
    let best_c = ref 0 and best_r = ref 0 in
    Array.iteri (fun i r ->
      if r > !best_r then begin best_c := i; best_r := r end
    ) p;
    (* Map back to original string *)
    let start = (!best_c - !best_r) / 2 in
    String.sub s start !best_r
  end

let () =
  let tests = [
    ("babad", "bab");
    ("cbbd",  "bb");
    ("racecar", "racecar");
    ("abacaba", "abacaba");
    ("a", "a");
    ("aabbaa", "aabbaa");
  ] in
  List.iter (fun (input, _expected) ->
    let result = longest_palindrome input in
    Printf.printf "longest_palindrome(%S) = %S\n" input result
  ) tests

Deep Comparison

OCaml vs Rust: Manacher Palindrome

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Return all palindromic substrings (not just the longest) sorted by length descending.

Count the total number of distinct palindromic substrings using the Manacher array.

Find the minimum number of cuts to partition a string into palindromes (use Manacher for O(n) palindrome detection + DP).

Implement Eertree (palindromic tree) as an alternative data structure and compare with Manacher.

Extend to report palindromes of a minimum length k efficiently without O(n) post-processing.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust