### Z Algorithm for String Prefix Matching (Rust)

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Computes the Z-array for a given string in O(n) time, where Z[i] is the length of the longest substring starting at index i that is also a prefix of the string. This is useful for pattern matching.

```Rust
use competitive_programming_rs::string::z_algorithm::z_algorithm::calc_z_array;

let text = "aabxaab";
let z = calc_z_array(text.as_bytes());
// z = [7, 1, 0, 0, 3, 1, 0]
// z[0] = 7 (entire string matches itself)
// z[1] = 1 ("a" matches prefix)
// z[4] = 3 ("aab" matches prefix)

// Pattern matching using Z-algorithm
fn z_search(text: &str, pattern: &str) -> Vec<usize> {
    let combined = format!("{}${{}}", pattern, text);
    let z = calc_z_array(combined.as_bytes());

    let mut matches = vec![];
    let pattern_len = pattern.len();
    for i in (pattern_len + 1)..combined.len() {
        if z[i] == pattern_len {
            matches.push(i - pattern_len - 1);
        }
    }
    matches
}

let text = "ababcabab";
let pattern = "ab";
let positions = z_search(text, pattern);
// positions = [0, 2, 5, 7] - all starting positions of "ab"
```

--------------------------------

### Implement Suffix Array and LCP Construction in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Provides tools for string indexing, including suffix array construction and Longest Common Prefix (LCP) array generation. Useful for pattern matching and substring analysis.

```rust
use competitive_programming_rs::data_structure::suffix_array::suffix_array::{SuffixArray, construct_lcp};

let text = "banana".as_bytes();
let sa = SuffixArray::new(text);
assert!(sa.contains("ana".as_bytes()));
let pattern = "an".as_bytes();
let lower = sa.lower_bound(pattern);
let upper = sa.upper_bound(pattern);
let lcp = construct_lcp(text, &sa.array);
```

--------------------------------

### Implement Sparse Table for Range Queries in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

A data structure for efficient range minimum/maximum queries on static arrays. It requires O(n log n) preprocessing time and provides O(1) query time.

```rust
use competitive_programming_rs::data_structure::sparse_table::sparse_table::SparseTable;
use std::cmp;

let values = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
let rmq = SparseTable::from(&values, i32::MAX, |a, b| cmp::min(a, b));
assert_eq!(rmq.get(0, 5), 1);
let rmq_max = SparseTable::from(&values, i32::MIN, |a, b| cmp::max(a, b));
assert_eq!(rmq_max.get(0, 10), 9);
```

--------------------------------

### Fast Fourier Transform (NTT) in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Implements the Number Theoretic Transform for fast polynomial multiplication in O(n log n) time. It is ideal for convolution tasks, large number multiplication, and frequency analysis.

```rust
use competitive_programming_rs::math::fast_fourier_transform::FastFourierTransform;

let fft = FastFourierTransform::new(998244353);
let a = vec![1, 2, 3, 4];
let b = vec![5, 6, 7, 8, 9];

let result = fft.convolution(&a, &b);
assert_eq!(result, vec![5, 16, 34, 60, 70, 70, 59, 36]);
```

--------------------------------

### Implement Fenwick Tree for Prefix Sums in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

A Fenwick Tree (Binary Indexed Tree) implementation for efficient prefix sum queries and point updates. It provides O(log n) performance for both update and range sum operations.

```rust
use competitive_programming_rs::data_structure::fenwick_tree::fenwick_tree::FenwickTree;

// Create a Fenwick tree with initializer function
let mut bit = FenwickTree::new(1000, || 0i64);

// Add values at specific indices
bit.add(0, 5);
bit.add(1, 3);
bit.add(2, 7);
bit.add(5, 10);

// Query prefix sum [0, 3) - returns 15 (5+3+7)
let prefix_sum = bit.sum_one(3);
assert_eq!(prefix_sum, 15);

// Query range sum [1, 6) - returns 20 (3+7+0+0+10)
let range_sum = bit.sum(1, 6);
assert_eq!(range_sum, 20);

// Useful for counting inversions, range frequency queries
for i in 0..100 {
    let value = i % 10;
    bit.add(value as usize, 1);
}
```

--------------------------------

### Find Shortest Path with Bellman-Ford in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Implements the Bellman-Ford algorithm to find shortest paths from a single source in a graph that may contain negative edge weights. It returns the distances and detects the presence of negative cycles in O(V * E) time.

```rust
use competitive_programming_rs::graph::shortest_path::bellman_ford::shortest_path;

const INF: i64 = 1 << 60;

// Create adjacency list: graph[u] = [(v, cost), ...]
let mut graph = vec![vec![]; 5];
graph[0].push((1, 2));
graph[0].push((2, 5));
graph[1].push((2, 1));
graph[1].push((3, 3));
graph[2].push((3, 1));
graph[3].push((4, 2));

// Find shortest paths from vertex 0
let (distances, negative_cycle) = shortest_path(&graph, 0, INF);

// distances[i] = shortest distance from source to vertex i
println!("Distance to vertex 4: {}", distances[4]);  // Output: 6

// negative_cycle[i] = true if vertex i is reachable via negative cycle
if negative_cycle.iter().any(|&b| b) {
    println!("Graph contains negative cycle!");
}

// Handle unreachable vertices
for (i, &dist) in distances.iter().enumerate() {
    if dist == INF {
        println!("Vertex {} is unreachable", i);
    }
}
```

--------------------------------

### Detect Bridges and Articulation Points in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Utilizes Tarjan's algorithm to identify bridges and articulation points in an undirected graph. It operates in O(V + E) time, making it suitable for large graph analysis.

```rust
use competitive_programming_rs::graph::bridge_detection::BridgeDetector;

let mut graph = vec![vec![]; 5];
let edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)];
for &(u, v) in &edges {
    graph[u].push(v);
    graph[v].push(u);
}

let detector = BridgeDetector::new(&graph);

for (a, b) in &detector.bridges {
    println!("Bridge: {} - {}", a, b);
}

for &v in &detector.articulations {
    println!("Articulation point: {}", v);
}
```

--------------------------------

### Perform Topological Sort in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Implements Kahn's algorithm to generate a topological ordering of a directed acyclic graph (DAG). The algorithm runs in O(V + E) time and is useful for scheduling tasks with dependencies.

```rust
use competitive_programming_rs::graph::topological_sort::topological_sort;

// Create DAG as adjacency list
let graph = vec![
    vec![1],     // 0 -> 1
    vec![2],     // 1 -> 2
    vec![],      // 2 has no outgoing edges
    vec![1, 4],  // 3 -> 1, 3 -> 4
    vec![5],     // 4 -> 5
    vec![2],     // 5 -> 2
];

// Get topological ordering
let order = topological_sort(&graph);
// order = [0, 3, 1, 4, 5, 2] (one valid ordering)

// Verify: for each edge u->v, u appears before v in order
let mut position = vec![0; 6];
for (i, &v) in order.iter().enumerate() {
    position[v] = i;
}
for (u, edges) in graph.iter().enumerate() {
    for &v in edges {
        assert!(position[u] < position[v]);
    }
}
```

--------------------------------

### Implement Dinitz Maximum Flow Algorithm in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

An efficient implementation of the Dinitz algorithm for finding the maximum flow in a network. It operates in O(V^2 * E) time and supports residual capacity analysis.

```rust
use competitive_programming_rs::graph::maximum_flow::dinitz::Dinitz;

let mut dinitz = Dinitz::new(6);
dinitz.add_edge(0, 1, 10);
dinitz.add_edge(0, 2, 10);
dinitz.add_edge(1, 2, 2);
dinitz.add_edge(1, 3, 4);
dinitz.add_edge(1, 4, 8);
dinitz.add_edge(2, 4, 9);
dinitz.add_edge(3, 5, 10);
dinitz.add_edge(4, 3, 6);
dinitz.add_edge(4, 5, 10);

let max_flow = dinitz.max_flow(0, 5);
println!("Maximum flow: {}", max_flow);
```

--------------------------------

### Implement Segment Tree for Range Queries in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

A segment tree implementation for efficient range queries with custom operators. It supports point updates and arbitrary range queries in O(log n) time complexity.

```rust
use competitive_programming_rs::data_structure::segment_tree::SegmentTree;

// Create a segment tree for range minimum queries
let mut seg = SegmentTree::new(10, |a: i64, b: i64| a.min(b));

// Update values at specific indices
seg.update(0, 5);
seg.update(1, 3);
seg.update(2, 7);
seg.update(3, 1);
seg.update(4, 9);

// Query minimum in range [0, 5) - returns Some(1)
let min_value = seg.query(0..5);
assert_eq!(min_value, Some(1));

// Query minimum in range [1, 3) - returns Some(3)
let min_value = seg.query(1..3);
assert_eq!(min_value, Some(3));

// Supports various range syntax
let min_all = seg.query(..);        // entire range
let min_to = seg.query(..3);        // [0, 3)
let min_from = seg.query(2..);      // [2, n)
let min_inclusive = seg.query(1..=3); // [1, 4)
```

--------------------------------

### Implement Union-Find (Disjoint Set Union) in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

A Union-Find data structure supporting path compression and union by size. It provides near O(1) amortized time complexity for connectivity queries and is suitable for Kruskal's algorithm.

```rust
use competitive_programming_rs::data_structure::union_find::UnionFind;

let mut uf = UnionFind::new(10);
assert!(uf.unite(0, 1));
assert!(uf.unite(2, 3));
assert!(uf.unite(0, 2));
assert_eq!(uf.find(0), uf.find(3));
assert_ne!(uf.find(0), uf.find(5));
assert!(!uf.unite(1, 3));

let mut edges = vec![(1, 0, 1), (2, 1, 2), (3, 0, 2)];
edges.sort();
let mut mst_weight = 0;
for (w, u, v) in edges {
    if uf.unite(u, v) {
        mst_weight += w;
    }
}
```

--------------------------------

### Implement Treap (Balanced BST) in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

A randomized balanced binary search tree that supports insertion, deletion, search, and k-th element queries. Operations are performed in O(log n) expected time.

```rust
use competitive_programming_rs::data_structure::treap::treap::Treap;

let mut treap = Treap::new(42);
assert!(treap.insert(5));
assert!(treap.insert(3));
assert!(treap.insert(8));
assert!(treap.insert(1));
assert!(treap.contains(&3));
assert_eq!(treap.nth(0), &1);
assert_eq!(treap.binary_search(&5), Ok(2));
assert_eq!(treap.erase(&3), Some(3));
assert_eq!(treap.len(), 3);
```

--------------------------------

### Convex Hull Computation using Andrew's Algorithm (Rust)

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Implements Andrew's monotone chain algorithm to compute the convex hull of a set of 2D points in O(n log n) time. It returns the indices of the points forming the hull in counter-clockwise order.

```Rust
use competitive_programming_rs::geometry::convex_hull::{extract_convex_hull, Point};

// Define points
let points = vec![
    Point { x: 0.0, y: 0.0 },
    Point { x: 1.0, y: 1.0 },
    Point { x: 2.0, y: 0.0 },
    Point { x: 1.0, y: 2.0 },
    Point { x: 1.0, y: 0.5 },  // interior point
];

// Get indices of points on convex hull
// contain_on_segment=true includes collinear points on edges
let hull_indices = extract_convex_hull(&points, false);

// hull_indices contains indices in counter-clockwise order
for &i in &hull_indices {
    println!("Hull point: ({}, {})", points[i].x, points[i].y);
}

// Calculate convex hull area using shoelace formula
fn hull_area(points: &[Point], hull: &[usize]) -> f64 {
    let n = hull.len();
    let mut area = 0.0;
    for i in 0..n {
        let p1 = &points[hull[i]];
        let p2 = &points[hull[(i + 1) % n]];
        area += p1.x * p2.y - p2.x * p1.y;
    }
    area.abs() / 2.0
}
```

--------------------------------

### Combination Calculator in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Calculates combinations (nCr) and combinations with repetition (nHr) efficiently by precomputing factorials. This is highly useful for counting problems and grid path calculations.

```rust
use competitive_programming_rs::math::combination::Combination;

const MOD: usize = 1_000_000_007;
let comb = Combination::new(1000, MOD);

let c_10_3 = comb.get(10, 3);
let h_5_3 = comb.h(5, 3);

println!("Paths in 10x15 grid: {}", comb.get(10 + 15, 10));
```

--------------------------------

### Decompose Strongly Connected Components in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Uses Kosaraju's algorithm to identify strongly connected components (SCCs) in a directed graph. The function returns component IDs for each vertex, allowing for quick connectivity checks in O(V + E) time.

```rust
use competitive_programming_rs::graph::strongly_connected_components::strongly_connected_components::decompose;

// Create directed graph as adjacency list
let graph = vec![
    vec![1],     // 0 -> 1
    vec![2],     // 1 -> 2
    vec![0, 3],  // 2 -> 0, 2 -> 3
    vec![4],     // 3 -> 4
    vec![5],     // 4 -> 5
    vec![3],     // 5 -> 3 (creates cycle 3->4->5->3)
];

// Get SCC component ID for each vertex
let component = decompose(&graph);

// Vertices in same component have same ID
// component is topologically sorted (smaller ID = later in topo order)
assert_eq!(component[0], component[1]);  // 0,1,2 form an SCC
assert_eq!(component[1], component[2]);
assert_eq!(component[3], component[4]);  // 3,4,5 form another SCC
assert_eq!(component[4], component[5]);

// Check if two vertices are strongly connected
fn same_scc(u: usize, v: usize, cmp: &[usize]) -> bool {
    cmp[u] == cmp[v]
}
```

--------------------------------

### Modular Integer Arithmetic in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Provides a wrapper type for modular arithmetic, supporting standard operators and exponentiation. It is essential for problems requiring calculations modulo a large prime.

```rust
use competitive_programming_rs::math::mod_int::mod_int::{set_mod_int, ModInt};

set_mod_int(1_000_000_007i64);

let a = ModInt::from(1_000_000_000i64);
let b = ModInt::from(500i64);

let sum = a + b;
let prod = a * b;
let power = ModInt::from(2i64).pow(30i64);

println!("Result: {}", power.value());
```

--------------------------------

### Rolling Hash for Substring Comparison (Rust)

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Implements a polynomial rolling hash using modular arithmetic with a large prime (2^61 - 1) to efficiently compare substrings and find patterns. It requires the input text as bytes and a base for hashing.

```Rust
use competitive_programming_rs::string::rolling_hash::rolling_hash::RollingHash;

const BASE: u64 = 1_000_000_007;

let text = "abracadabra";
let hash = RollingHash::new(text.as_bytes(), BASE);

// Get hash of substring [l, r)
let hash_abra_1 = hash.get_hash(0, 4);   // "abra" at position 0
let hash_abra_2 = hash.get_hash(7, 11);  // "abra" at position 7

// Same substrings have same hash
assert_eq!(hash_abra_1, hash_abra_2);

// Different substrings have different hash (with high probability)
let hash_brac = hash.get_hash(1, 5);     // "brac"
assert_ne!(hash_abra_1, hash_brac);

// Efficient pattern matching
fn find_pattern(text: &str, pattern: &str, base: u64) -> Vec<usize> {
    let text_hash = RollingHash::new(text.as_bytes(), base);
    let pattern_hash = RollingHash::new(pattern.as_bytes(), base);
    let target = pattern_hash.get_hash(0, pattern.len());

    let mut matches = vec![];
    for i in 0..=(text.len() - pattern.len()) {
        if text_hash.get_hash(i, i + pattern.len()) == target {
            matches.push(i);
        }
    }
    matches
}
```

--------------------------------

### Implement Lazy Segment Tree for Range Updates in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

A segment tree with lazy propagation for efficient range updates and range queries. It supports operations like range addition or updates with O(log n) complexity for both operations.

```rust
use competitive_programming_rs::data_structure::lazy_segment_tree::lazy_segment_tree::LazySegmentTree;

const INF: i64 = 1 << 60;

// Create lazy segment tree for range minimum with range addition
let mut seg_min = LazySegmentTree::new(
    10,                          // size
    || INF,                      // identity element for query
    |&s, &t| s.min(t),          // merge operation
    |&f, &x| f + x,             // apply lazy to element
    |&f, &g| f + g,             // compose lazy values
    || 0,                        // identity for lazy
);

// Set initial values
for i in 0..10 {
    seg_min.set(i, i as i64);
}

// Add 5 to all elements in range [2, 7)
seg_min.apply_range(2..7, 5);

// Query minimum in range [0, 10) after update
let result = seg_min.prod(0..10);

// Query minimum in range [2, 7) - returns 7 (original 2 + 5)
let result = seg_min.prod(2..7);

// Get all elements' aggregate
let all_min = seg_min.all_prod();
```

--------------------------------

### Query Lowest Common Ancestor in Rust

Source: https://context7.com/kenkoooo/competitive-programming-rs/llms.txt

Provides a structure to perform O(log n) LCA queries on a tree after O(n log n) preprocessing. It also supports calculating the distance between any two nodes in the tree.

```rust
use competitive_programming_rs::graph::lca::lca::LowestCommonAncestor;

// Create tree as adjacency list (undirected edges)
let mut graph = vec![vec![]; 7];
// Tree structure:
//       0
//      / \
//     1   2
//    /|\   \
//   3 4 5   6
graph[0].push(1); graph[1].push(0);
graph[0].push(2); graph[2].push(0);
graph[1].push(3); graph[3].push(1);
graph[1].push(4); graph[4].push(1);
graph[1].push(5); graph[5].push(1);
graph[2].push(6); graph[6].push(2);

// Build LCA structure (assumes root is vertex 0)
let lca = LowestCommonAncestor::new(&graph);

// Query LCA of two vertices
assert_eq!(lca.get_lca(3, 5), 1);  // LCA of 3 and 5 is 1
assert_eq!(lca.get_lca(3, 6), 0);  // LCA of 3 and 6 is 0
assert_eq!(lca.get_lca(4, 5), 1);  // LCA of 4 and 5 is 1

// Query distance between vertices
assert_eq!(lca.get_dist(3, 5), 2);  // 3 -> 1 -> 5
assert_eq!(lca.get_dist(3, 6), 4);  // 3 -> 1 -> 0 -> 2 -> 6
```

=== COMPLETE CONTENT === This response contains all available snippets from this library. No additional content exists. Do not make further requests.