Skip to Content
ReferenceLibrary

strings

self written n times in a row, as a new Str: "0".repeat(4) is "0000".

Generated from spec/std/strings.cp by cpl doc --format json.

KmpAutomaton

pub struct KmpAutomaton<A>

O(|pat| * |A|). Prefix (KMP) automaton over alphabet domain A, for O(1) transitions in DP.

Source

KmpAutomaton.new

fn new<S: Seq>(pat: S) -> KmpAutomaton<A>

The KMP automaton of pat over the alphabet domain A: one state per matched prefix length 0..=pat.len, with a full transition table. Call it as KmpAutomaton<A>(pat).

  • cost: O(|pat| * |A|)
  • empty: an empty pat gives one state, 0, which matches everywhere
  • traps: when an element of pat is not in A

Examples:

  • KmpAutomaton<Char>("aba").len == 4

Source

KmpAutomaton.len

fn len(self) -> Int

The number of states, pat.len + 1; the states are 0..=pat.len and pat.len means a full match.

  • cost: O(1)
  • traps: never

Examples:

  • KmpAutomaton<Char>("ab").len == 3

Source

KmpAutomaton.step

fn step(self, state: Int, a: A) -> Int

The matched prefix length after reading a in state. From the full-match state the automaton falls back along link first, so matching continues and overlaps are found.

  • cost: O(1)
  • traps: when state is outside 0..self.len

Examples:

  • let k = KmpAutomaton<Char>("aba"); k.step(3, 'b') == 2 and k.step(0, 'b') == 0

Source

fn link(self, state: Int) -> Int

The failure link of state: the length of the longest proper border of pat[..state], and 0 at state 0. It equals prefix_function(pat)[state - 1] for state >= 1.

  • cost: O(1)
  • traps: when state is outside 0..self.len

Examples:

  • let k = KmpAutomaton<Char>("aba"); k.link(3) == 1 and k.link(2) == 0

Source

KmpAutomaton.find_all

fn find_all<S: Seq>(self, text: S) -> yields Int

The start position (0-based, counted in text's iteration order) of every occurrence of pat in text, overlapping ones included.

  • cost: O(|text|)
  • empty: an empty text yields nothing unless pat is empty; an empty pat yields 0..=|text|
  • ties: every occurrence is yielded; None is preferred
  • order: increasing start
  • traps: when an element of text is not in A

Examples:

  • KmpAutomaton<Char>("aba").find_all("ababa").collect() == [0, 2]

Source

Palindromes

pub struct Palindromes(odd: List<Int>, even: List<Int>)

O(n) space, O(1) queries. Manacher palindrome radii. odd[i] is the number of palindromes centred on s[i]; even[i] is the number centred between s[i - 1] and s[i].

Source

Palindromes.len

fn len(self) -> Int

The length of the sequence the radii were computed for.

  • cost: O(1)
  • traps: never

Examples:

  • manacher("aba").len == 3

Source

Palindromes.is_empty

fn is_empty(self) -> Bool

True when the sequence the radii were computed for is empty.

  • cost: O(1)
  • traps: never

Examples:

  • manacher("").is_empty == true

Source

Palindromes.longest_at

fn longest_at(self, i: Int) -> Int

Source

Palindromes.longest_between

fn longest_between(self, i: Int) -> Int

Source

Palindromes.is_palindrome

fn is_palindrome<R>(self, r: R) -> Bool

True when the positions r (l..r, l..=r, or a Range<D>) of the original sequence form a palindrome: p.is_palindrome(l..r) == is_palindrome(s[l..r]).

  • cost: O(1)
  • traps: when r reaches outside 0..=self.len

Examples:

  • let p = manacher("abacaba"); p.is_palindrome(0..3) and not p.is_palindrome(1..4)

Source

Palindromes.count

fn count(self) -> Int

The number of non-empty palindromic substrings, each occurrence counted: sum(odd) + sum(even).

  • cost: O(n)
  • traps: never

Examples:

  • manacher("aaa").count() == 6

Source

Palindromes.longest

fn longest(self) -> (l: Int, r: Int)

The half-open range (l, r) of a longest palindromic substring.

  • cost: O(n)
  • ties: the leftmost (smallest l)
  • traps: never

Examples:

  • manacher("abacdc").longest() == (0, 3)
  • manacher("").longest() == (0, 0)

Source

SuffixArray

pub struct SuffixArray

O(n) SA-IS + Kasai LCP (O(n log n) with RMQ). Suffix array, inverse rank, adjacent LCP, and O(1) LCP/comparison queries.

Source

SuffixArray.new

fn new<S: Indexed>(s: S) -> SuffixArray

The suffix array of s with its inverse and LCP array: sa[r] is the start of the suffix of rank r, rank[sa[r]] == r, and lcp[r] is the LCP of the suffixes of ranks r and r + 1. Call it as SuffixArray(s); positions count from 0.

Elements are compared by Ord, so a shorter suffix that is a prefix of a longer one ranks first.

  • cost: O(n) for Str and small integer alphabets, O(n log n) otherwise
  • empty: sa, rank and lcp all empty
  • traps: never

Examples:

  • SuffixArray("banana").sa == [5, 3, 1, 0, 4, 2]
  • SuffixArray("banana").lcp == [1, 3, 0, 0, 2]

Source

SuffixArray.len

fn len(self) -> Int

The length n of the sequence the suffix array was built over.

  • cost: O(1)
  • traps: never

Examples:

  • SuffixArray("banana").len == 6

Source

SuffixArray.is_empty

fn is_empty(self) -> Bool

True when the suffix array was built over an empty sequence.

  • cost: O(1)
  • traps: never

Examples:

  • SuffixArray("").is_empty == true

Source

SuffixArray.lcp_between

fn lcp_between(self, i: Int, j: Int) -> Int

The length of the longest common prefix of the suffixes starting at i and j. The empty suffix at n is allowed, and lcp_between(i, i) == n - i.

  • cost: O(1)
  • traps: when i or j is outside 0..=self.len

Examples:

  • SuffixArray("banana").lcp_between(1, 3) == 3

Source

SuffixArray.rank_range

fn rank_range<P: Indexed>(self, pat: P) -> Range<Int>

The ranks lo..hi of the suffixes that start with pat. When there are None it is the empty range at the rank where pat would sort.

  • cost: O(|pat| log n)
  • empty: an empty pat gives 0..n
  • order: a range of ranks, increasing
  • traps: never

Examples:

  • SuffixArray("banana").rank_range("ana") == 1..3
  • SuffixArray("banana").rank_range("c") == 4..4

Source

SuffixArray.find_all

fn find_all<P: Indexed>(self, pat: P) -> yields Int

The start of every occurrence of pat, read off sa over rank_range(pat).

  • cost: O(|pat| log n + occurrences)
  • empty: an empty pat yields every start 0..n (not the end position n)
  • ties: every occurrence is yielded; None is preferred
  • order: suffix-array order (by rank), not by position
  • traps: never

Examples:

  • SuffixArray("banana").find_all("ana").collect() == [3, 1]

Source

SuffixArray.count

fn count<P: Indexed>(self, pat: P) -> Int

The number of occurrences of pat, overlapping ones included: rank_range(pat).len.

  • cost: O(|pat| log n)
  • empty: an empty pat gives n
  • traps: never

Examples:

  • SuffixArray("banana").count("an") == 2

Source

SuffixArray.lcp_range

fn lcp_range(self, i: Int, len: Int) -> Range<Int>

The ranks lo..hi of the suffixes whose LCP with the suffix at i is at least len; always contains rank[i].

  • cost: O(log n)
  • order: a range of ranks, increasing; it holds rank[i]
  • traps: when i is outside 0..n or len outside 0..=n - i

Examples:

  • SuffixArray("banana").lcp_range(1, 3) == 1..3

Source

SuffixArray.compare

fn compare(self, l1: Int, r1: Int, l2: Int, r2: Int) -> Int

The lexicographic comparison of s[l1..r1] and s[l2..r2]: -1, 0 or 1. A proper prefix compares less.

  • cost: O(1)
  • traps: when a range is not within 0..=n or has its end before its start

Examples:

  • SuffixArray("banana").compare(1, 3, 3, 5) == 0
  • SuffixArray("banana").compare(1, 2, 1, 3) == -1

Source

SuffixArray.arg_min

fn arg_min(self, lo: Int, hi: Int) -> Int

Source

SuffixArray.distinct

fn distinct(self) -> Int

The number of distinct non-empty substrings: n * (n + 1) / 2 - sum(lcp).

  • cost: O(n)
  • traps: never

Examples:

  • SuffixArray("banana").distinct() == 15

Source

SuffixArray.lcp_of_ranks

fn lcp_of_ranks(self, r: Range<Int>) -> Int

The longest prefix common to every suffix with rank in r: the minimum of lcp[j] for j in r.start..r.end - 1, or the suffix's own length when r holds one rank.

  • cost: O(1)
  • empty: an empty r traps
  • traps: when r is empty or reaches outside 0..n

Examples:

  • SuffixArray("banana").lcp_of_ranks(1..3) == 3
  • SuffixArray("banana").lcp_of_ranks(3..4) == 6

Source

SuffixArray.split

fn split(self, r: Range<Int>) -> Int

Where the rank range r splits in the suffix tree: the k in r.start + 1..r.end whose adjacent LCP lcp[k - 1] equals lcp_of_ranks(r), so r.start..k and k..r.end are the first child and the rest.

  • cost: O(1)
  • empty: an r with fewer than two ranks traps
  • ties: the smallest such k
  • traps: when r.len < 2 or r reaches outside 0..n

Examples:

  • SuffixArray("banana").split(0..3) == 1
  • SuffixArray("banana").split(0..6) == 3

Source

SuffixArray.kth_distinct

fn kth_distinct(self, k: Int) -> ?Range<Int>

The k-th (0-based) lexicographically smallest distinct non-empty substring, as the positions l..r of one occurrence, or None when k >= distinct().

  • cost: O(log n)
  • ties: the occurrence in the suffix of smallest rank that holds it
  • order: k counts in increasing lexicographic order; the range is increasing positions
  • traps: when k < 0

Examples:

  • SuffixArray("banana").kth_distinct(1) == Some(3..5)
  • SuffixArray("banana").kth_distinct(15) == None

Source

SuffixTreeEdge

pub struct SuffixTreeEdge(

O(1) value. One edge of the compressed suffix tree of a sequence, built in O(n) from SA + LCP.

Source

HashVal

pub struct HashVal(h1: Int, h2: Int)

O(1) space and comparison. A 64-bit double-mod polynomial hash value (Copy + Eq + Ord + Hash). Can itself be fed into another RollingHash (e.g. hashing rows into a column hash for 2D grids).

Source

HashVal.hash_token

fn hash_token(self) -> Int

One integer that identifies the pair, (h1 << 31) | h2, so a RollingHash can hash a sequence of HashVal (rows of a grid, say).

  • cost: O(1)
  • traps: never

Examples:

  • HashVal(1, 2).hash_token == 2147483650

Source

Hashable

pub trait Hashable

O(1) per element. Elements accepted by RollingHash: Char, Int, Bool, HashVal, or any user type implementing hash_token.

Source

Hashable.hash_token

fn hash_token(self) -> Int

Source

RollingHash

pub struct RollingHash

O(n) build, O(1) slice hash. Generalized double-mod polynomial rolling hash over Str, List<T>, or any [D]T (Char, Int, Bool, HashVal).

Built in O(n); substring queries .get(l..r) / .slice(l, r) and .combine(a, b, b_len) are O(1). Each constructor draws independent random salted bases unless bases: is passed explicitly, so 2D row and column hashes never collide on transposes.

Source

RollingHash.new

fn new<S: Seq>(seq: S, bases: ?(Int, Int) = None) -> RollingHash

Source

RollingHash.push

fn push<T: Hashable>(mut self, x: T)

Appends x to the end of the hashed sequence.

  • cost: O(1) amortized
  • traps: never

Examples:

  • var h = RollingHash("ab"); h.push('a'); h.all == h.hash_of("aba")

Source

RollingHash.pop

fn pop(mut self)

Removes the last element of the hashed sequence.

  • cost: O(1)
  • traps: when the hash is empty

Examples:

  • var h = RollingHash("abc"); h.pop(); h.all == h.hash_of("ab")

Source

RollingHash.hash_of

fn hash_of<S: Seq>(self, seq: S) -> HashVal

The hash seq would have under self's bases, without building a RollingHash of it; compare it with any slice of self.

  • cost: O(|seq|)
  • empty: HashVal(0, 0)
  • traps: never

Examples:

  • let h = RollingHash("xab"); h.hash_of("ab") == h.get(1..3)

Source

RollingHash.concat

fn concat(self, parts: List<(hash: HashVal, len: Int)>) -> HashVal

The hash of the concatenation of parts, each given as its hash and length, under self's bases; combine folded left to right.

  • cost: O(|parts|) amortized
  • empty: HashVal(0, 0)
  • traps: when a len is negative

Examples:

  • let h = RollingHash("abcd"); h.concat([(h.get(0..2), 2), (h.get(2..4), 2)]) == h.all

Source

RollingHash.len

fn len(self) -> Int

The number of elements hashed.

  • cost: O(1)
  • traps: never

Examples:

  • RollingHash("abc").len == 3

Source

RollingHash.is_empty

fn is_empty(self) -> Bool

True when no elements are hashed.

  • cost: O(1)
  • traps: never

Examples:

  • RollingHash("").is_empty == true

Source

RollingHash.all

fn all(self) -> HashVal

The hash of the whole sequence, self.get(0..self.len).

  • cost: O(1)
  • traps: never

Examples:

  • let h = RollingHash("abc"); h.all == h.get(0..3)

Source

RollingHash.raw_slice

fn raw_slice(self, l: Int, r: Int) -> HashVal

Source

RollingHash.eq_sub

fn eq_sub(self, a: Int, b: Int, len: Int) -> Bool

Source

RollingHash.slice

fn slice(self, l: Int, r: Int) -> HashVal

The hash of the half-open slice l..r (0-based); HashVal(0, 0) when l == r.

  • cost: O(1)
  • traps: when l > r, l < 0 or r > self.len

Examples:

  • let h = RollingHash("abab"); h.slice(0, 2) == h.slice(2, 4) and h.slice(1, 1) == HashVal(0, 0)

Source

RollingHash.get

fn get<R>(self, r: R) -> HashVal

The hash of a range of positions: l..r, l..=r, ..k, k.., or a Range<D> when the hash was built over a [D]T. The same value as slice.

  • cost: O(1)
  • traps: when the range reaches outside the hashed sequence

Examples:

  • let h = RollingHash("abab"); h.get(0..2) == h.get(2..=3)

Source

RollingHash.combine

fn combine(self, a: HashVal, b: HashVal, b_len: Int) -> HashVal

The hash of a's sequence followed by b's, where b has length b_len: a * base^b_len + b per modulus.

  • cost: O(1) amortized (the power table grows past len on demand)
  • traps: when b_len < 0

Examples:

  • let h = RollingHash("abc"); h.combine(h.get(0..1), h.get(1..3), 2) == h.all

Source

RollingHash.lcp

fn lcp(self, a: Int, b: Int) -> Int

The length of the longest common prefix of the suffixes starting at a and b, by binary search on hashes (so it can be wrong on a collision).

  • cost: O(log n)
  • traps: when a or b is outside 0..=self.len

Examples:

  • RollingHash("abcabd").lcp(0, 3) == 2

Source

RollingHash.lcs

fn lcs(self, a: Int, b: Int) -> Int

The length of the longest common suffix of the prefixes s[..a] and s[..b], by binary search on hashes.

  • cost: O(log n)
  • traps: when a or b is outside 0..=self.len

Examples:

  • RollingHash("xabyab").lcs(3, 6) == 2

Source

RollingHash.lcp_with

fn lcp_with(self, a: Int, other: RollingHash, b: Int) -> Int

The length of the longest common prefix of self[a..] and other[b..], by binary search on hashes. Both hashes must use the same bases.

  • cost: O(log min(|self| - a, |other| - b))
  • traps: when the bases differ, a is outside 0..=self.len or b outside 0..=other.len

Examples:

  • RollingHash("abcd", bases: Some((131, 137))).lcp_with(1, RollingHash("xbcx", bases: Some((131, 137))), 1) == 2

Source

Hash2D

pub struct Hash2D<R, C>(bases: (Int, Int))

O(R * C) build, O(1) rectangle hash. Double-mod 2D polynomial prefix hash over a grid with row domain R and column domain C. Built in O(R * C); rect(rows, cols) is O(1) and returns a HashVal.

Source

Hash2D.new

fn new(code: (R, C) -> Int, bases: ?(Int, Int) = None) -> Hash2D<R, C>

Source

Hash2D.rect

fn rect(self, rows: Range<R>, cols: Range<C>) -> HashVal

Source

Hash61

pub struct Hash61(v

O(1) value. Single-modulus 2^61 - 1 (Mersenne prime) polynomial hash value (Copy + Eq + Ord + Hash).

Source

RollingHash61

pub struct RollingHash61

O(n) build, O(1) query. Single-modulus 2^61 - 1 polynomial rolling hash with randomized base.

Source

RollingHash61.new

fn new<S: Seq>(seq: S, base: ?U64 = None) -> RollingHash61

A single-modulus polynomial rolling hash of seq modulo the Mersenne prime 2^61 - 1; call it as RollingHash61(seq). Same scheme as RollingHash with one modulus: each token enters as token % M + 1; the base is drawn at random unless base: gives it.

  • cost: O(n)
  • empty: an empty hash; push can grow it
  • traps: when a given base is outside 2..2^61 - 1

Examples:

  • let h = RollingHash61("abab"); h.get(0..2) == h.get(2..4)

Source

RollingHash61.len

fn len(self) -> Int

The number of elements hashed.

  • cost: O(1)
  • traps: never

Examples:

  • RollingHash61("abc").len == 3

Source

RollingHash61.is_empty

fn is_empty(self) -> Bool

True when no elements are hashed.

  • cost: O(1)
  • traps: never

Examples:

  • RollingHash61("").is_empty == true

Source

RollingHash61.slice61

fn slice61(self, l: Int, r: Int) -> Hash61

Source

RollingHash61.all

fn all(self) -> Hash61

The hash of the whole sequence, self.get(0..self.len).

  • cost: O(1)
  • traps: never

Examples:

  • let h = RollingHash61("abc"); h.all == h.get(0..3)

Source

RollingHash61.get

fn get<R>(self, r: R) -> Hash61

The hash of a range of positions (l..r, l..=r, ..k, k.., or a Range<D> when built over a [D]T); an empty range hashes to Hash61(0).

  • cost: O(1)
  • traps: when the range reaches outside the hashed sequence

Examples:

  • let h = RollingHash61("abab"); h.get(0..2) == h.get(2..=3)

Source

RollingHash61.combine

fn combine(self, a: Hash61, b: Hash61, b_len: Int) -> Hash61

The hash of a's sequence followed by b's, where b has length b_len: a * base^b_len + b modulo 2^61 - 1.

  • cost: O(1) amortized (the power table grows past len on demand)
  • traps: when b_len < 0

Examples:

  • let h = RollingHash61("abc"); h.combine(h.get(0..1), h.get(1..3), 2) == h.all

Source

RollingHash61.push

fn push<T: Hashable>(mut self, x: T)

Appends x to the end of the hashed sequence.

  • cost: O(1) amortized
  • traps: never

Examples:

  • var h = RollingHash61("ab"); h.push('a'); h.push('b'); h.get(0..2) == h.get(2..4)

Source

RollingHash61.pop

fn pop(mut self)

Removes the last element of the hashed sequence.

  • cost: O(1)
  • traps: when the hash is empty

Examples:

  • var h = RollingHash61("abab"); h.pop(); h.len == 3

Source

RollingHash61.lcp

fn lcp(self, a: Int, b: Int) -> Int

The length of the longest common prefix of the suffixes starting at a and b, by binary search on hashes.

  • cost: O(log n)
  • traps: when a or b is outside 0..=self.len

Examples:

  • RollingHash61("abcabd").lcp(0, 3) == 2

Source

RollingHash61.lcs

fn lcs(self, a: Int, b: Int) -> Int

The length of the longest common suffix of the prefixes s[..a] and s[..b], by binary search on hashes.

  • cost: O(log n)
  • traps: when a or b is outside 0..=self.len

Examples:

  • RollingHash61("xabyab").lcs(3, 6) == 2

Source

RollingHash61.lcp_with

fn lcp_with(self, a: Int, other: RollingHash61, b: Int) -> Int

The length of the longest common prefix of self[a..] and other[b..], by binary search on hashes. Both hashes must use the same base.

  • cost: O(log min(|self| - a, |other| - b))
  • traps: when the bases differ, a is outside 0..=self.len or b outside 0..=other.len

Examples:

  • RollingHash61("abcd", base: Some(U64(131))).lcp_with(1, RollingHash61("xbcx", base: Some(U64(131))), 1) == 2

Source

DynamicHash

pub struct DynamicHash<D>

O(n) build, O(log n) point update and range hash. Mutable double-mod rolling hash over domain D. Supports h[i] = x via W8 IndexSet.

Source

DynamicHash.new

fn new<S: Indexed>(seq: S, bases: ?(Int, Int) = None) -> DynamicHash<D>

A double-modulus rolling hash of seq that supports point updates, kept forwards and backwards in a segment tree; call it as DynamicHash(seq). Positions are seq's keys (domain D); hashes follow the RollingHash scheme and bases.

  • cost: O(n)
  • empty: an empty hash
  • traps: when a given base is outside 2..M

Examples:

  • let h = DynamicHash("abab"); h.get(0..2) == h.get(2..4)

Source

DynamicHash.len

fn len(self) -> Int

The number of hashed positions, D.K.

  • cost: O(1)
  • traps: never

Examples:

  • DynamicHash("abc").len == 3

Source

DynamicHash.is_empty

fn is_empty(self) -> Bool

True when there are no positions.

  • cost: O(1)
  • traps: never

Examples:

  • DynamicHash("").is_empty == true

Source

DynamicHash.all

fn all(self) -> HashVal

The hash of the whole sequence, self.get(..).

  • cost: O(1)
  • traps: never

Examples:

  • let h = DynamicHash("abab"); h.all == h.get(0..4)

Source

DynamicHash.set

fn set<T: Hashable>(mut self, i: D, x: T)

Replaces the element at position i with x; h[i] = x means the same.

  • cost: O(log n)
  • traps: never (i is a D)

Examples:

  • var h = DynamicHash("abxb"); h.set(2, 'a'); h.get(0..2) == h.get(2..4)

Source

DynamicHash.get

fn get(self, r: Range<D>) -> HashVal

The hash of the elements over r in order (a cut range j..i works too, decision 124).

  • cost: O(log n)
  • empty: an empty r gives HashVal(0, 0)
  • traps: never (r is a Range<D>)

Examples:

  • let h = DynamicHash("xyxy"); h.get(0..2) == h.get(2..4)

Source

DynamicHash.rev_get

fn rev_get(self, r: Range<D>) -> HashVal

The hash of the elements over r read backwards, comparable with get.

  • cost: O(log n)
  • empty: an empty r gives HashVal(0, 0)
  • traps: never (r is a Range<D>)

Examples:

  • let h = DynamicHash("abba"); h.rev_get(0..2) == h.get(2..4)

Source

DynamicHash.is_palindrome

fn is_palindrome(self, r: Range<D>) -> Bool

True when the elements over r read the same both ways: get(r) == rev_get(r).

  • cost: O(log n)
  • empty: true for an empty r
  • traps: never (r is a Range<D>)

Examples:

  • let h = DynamicHash("abca"); h.is_palindrome(1..2) and not h.is_palindrome(0..4)

Source

SuffixAutomaton

pub struct SuffixAutomaton<A>

O(n * |A|) space, O(1) amortized push. Online suffix automaton over alphabet domain A. O(n * |A|) flat memory, O(n) amortized build, O(states) topo_order and occurrences.

Source

SuffixAutomaton.new

fn new() -> SuffixAutomaton<A>

An empty suffix automaton over the alphabet domain A: only the root state 0. Call it as SuffixAutomaton<A>(), then push letters.

  • cost: O(|A|)
  • traps: never

Examples:

  • SuffixAutomaton<Char>().len == 1

Source

SuffixAutomaton.of

fn of<S: Seq>(s: S) -> SuffixAutomaton<A>

The suffix automaton of s: SuffixAutomaton<A>() followed by push of each element.

States are numbered in creation order: each push creates its new state, then the clone if one is needed. For "abb" the states are 0 (empty), 1 (a), 2 (ab), 3 (abb, bb) and 4 (b, the clone).

  • cost: O(|s| * |A|) memory, O(|s|) amortized time
  • empty: only the root
  • traps: when an element of s is not in A

Examples:

  • SuffixAutomaton<Char>.of("abb").len == 5

Source

SuffixAutomaton.add_empty_state

fn add_empty_state(mut self, length: Int, is_prefix: Bool) -> Int

Source

SuffixAutomaton.clone_state

fn clone_state(mut self, src: Int, length: Int) -> Int

Source

SuffixAutomaton.push

fn push(mut self, a: A)

Source

SuffixAutomaton.root

fn root(self) -> Int

The root state, for the empty string: always 0.

  • cost: O(1)
  • traps: never

Examples:

  • SuffixAutomaton<Char>.of("ab").root == 0

Source

SuffixAutomaton.len

fn len(self) -> Int

The number of states, the root included; at most max(1, 2n - 1).

  • cost: O(1)
  • traps: never

Examples:

  • SuffixAutomaton<Char>.of("abb").len == 5

Source

SuffixAutomaton.step

fn step(self, state: Int, a: A) -> ?Int

Source

fn link(self, state: Int) -> ?Int

Source

SuffixAutomaton.longest

fn longest(self, state: Int) -> Int

Source

SuffixAutomaton.shortest

fn shortest( self, state: Int, ) -> Int

Source

SuffixAutomaton.first_pos

fn first_pos(self, state: Int) -> Int

Source

SuffixAutomaton.find

fn find<S: Seq>(self, word: S) -> ?Int

Source

SuffixAutomaton.contains

fn contains<S: Seq>(self, word: S) -> Bool

True when word is a substring of the automaton's string: find(word) != None.

  • cost: O(|word|)
  • empty: true for an empty word
  • traps: when an element of word is not in A

Examples:

  • let m = SuffixAutomaton<Char>.of("abb"); m.contains("ab") and not m.contains("ba")

Source

SuffixAutomaton.distinct

fn distinct(self) -> Int

The number of distinct non-empty substrings: the sum of longest(v) - shortest(v) + 1 over the states other than the root.

  • cost: O(states)
  • traps: never

Examples:

  • SuffixAutomaton<Char>.of("abb").distinct() == 5

Source

SuffixAutomaton.topo_order

fn topo_order(self) -> List<Int>

Source

SuffixAutomaton.occ_counts

fn occ_counts(self) -> List<Int>

Source

SuffixAutomaton.lcs

fn lcs<S: Seq>(self, other: S) -> (len: Int, end: Int)

Source

SuffixAutomaton.reset

fn reset(mut self)

Moves the append point back to the root, so the next push starts a new word of a generalized automaton (the substrings of all words added so far).

  • cost: O(1)
  • traps: never

Examples:

  • var m = SuffixAutomaton<Char>.of("ab"); m.reset(); m.push('c'); m.contains("c") and not m.contains("bc")

Source

SuffixAutomaton.add_word

fn add_word<S: Seq>(mut self, word: S)

Adds word as a separate word of a generalized automaton: reset(), then push each letter. Afterwards the automaton holds the substrings of every word added.

  • cost: O(|word|) amortized
  • empty: an empty word only resets
  • traps: when an element of word is not in A

Examples:

  • var m = SuffixAutomaton<Char>(); m.add_word("ab"); m.add_word("b"); m.distinct() == 3

Source

SuffixAutomaton.states

fn states(self) -> yields Int

Every state in the order of topo_order, lazily.

  • cost: O(states)
  • order: non-decreasing longest; ties by smaller state number
  • traps: never

Examples:

  • SuffixAutomaton<Char>.of("abb").states().collect() == [0, 1, 4, 2, 3]

Source

SuffixAutomaton.endpos_tree

fn endpos_tree(self) -> List<List<Int>>

The suffix-link tree as child lists: entry v lists the states whose link is v. Rooted at 0.

  • cost: O(states)
  • order: keyed by state; each child list in increasing state number
  • traps: never

Examples:

  • SuffixAutomaton<Char>.of("abb").endpos_tree() == [[1, 4], [], [], [], [2, 3]]

Source

SuffixAutomaton.kth_substring

fn kth_substring(self, k: Int, distinct: Bool = true) -> ?List<A>

The k-th (0-based) non-empty substring in lexicographic order, as its letters, or None when there are not that many. With distinct: false each substring counts once per occurrence. A proper prefix comes before its extensions.

  • cost: O(states * |A|)
  • ties: with distinct: false, copies of one substring are adjacent and interchangeable
  • order: the letters of the substring, first to last
  • traps: when k < 0

Examples:

  • SuffixAutomaton<Char>.of("abb").kth_substring(3) == Some(['b'])
  • SuffixAutomaton<Char>.of("abb").kth_substring(5, distinct: false) == Some(['b', 'b'])

Source

PalindromicTree

pub struct PalindromicTree<A>

O(n * |A|) space, O(1) amortized push. Online palindromic tree (eertree) over alphabet domain A, with diff and series_link for O(n log n) palindromic partition DP. State 0 is the odd root (pal_len == -1); state 1 is the even root (pal_len == 0).

Source

PalindromicTree.new

fn new() -> PalindromicTree<A>

An empty palindromic tree over the alphabet domain A: just the odd root 0 and the even root 1. Call it as PalindromicTree<A>().

  • cost: O(|A|)
  • traps: never

Examples:

  • PalindromicTree<Char>().len == 2

Source

PalindromicTree.of

fn of<S: Seq>(s: S) -> PalindromicTree<A>

The palindromic tree of s: PalindromicTree<A>() followed by push of each element. New states are numbered from 2 in creation order.

  • cost: O(|s| * |A|) memory, O(|s|) amortized time
  • empty: just the two roots
  • traps: when an element of s is not in A

Examples:

  • PalindromicTree<Char>.of("aba").distinct == 3

Source

PalindromicTree.push

fn push(mut self, a: A) -> Int

Source

PalindromicTree.size

fn size(self) -> Int

Source

PalindromicTree.at

fn at(self, i: Int) -> A

Source

PalindromicTree.grow

fn grow(mut self, cur: Int, c: Int, link_to: Int)

Source

PalindromicTree.len

fn len(self) -> Int

The number of states, both roots included: distinct + 2.

  • cost: O(1)
  • traps: never

Examples:

  • PalindromicTree<Char>.of("aba").len == 5

Source

PalindromicTree.distinct

fn distinct(self) -> Int

The number of distinct non-empty palindromic substrings, len - 2; at most n.

  • cost: O(1)
  • traps: never

Examples:

  • PalindromicTree<Char>.of("aba").distinct == 3

Source

PalindromicTree.pal_len

fn pal_len(self, state: Int) -> Int

Source

fn link(self, state: Int) -> Int

Source

PalindromicTree.step

fn step(self, state: Int, a: A) -> ?Int

Source

PalindromicTree.diff

fn diff(self, state: Int) -> Int

Source

fn series_link(self, state: Int) -> Int

Source

PalindromicTree.occ_counts

fn occ_counts(self) -> List<Int>

Source

PalindromicTree.push_front

fn push_front(mut self, a: A) -> Int

Prepends the letter a (a double-ended tree) and returns the state of the longest palindromic prefix of the new string, creating it if it is new.

  • cost: O(1) amortized
  • traps: never (a is an A)

Examples:

  • var t = PalindromicTree<Char>.of("ba"); t.push_front('a') == 4

Source

PalindromicTree.pop

fn pop(mut self)

Undoes the most recent push not yet undone, removing the state it created if any, so a DFS over a tree of strings can back out.

  • cost: O(1) amortized
  • traps: when there is no push to undo

Examples:

  • var t = PalindromicTree<Char>.of("ab"); t.pop(); t.distinct == 1 and t.last_state == 2

Source

PalindromicTree.last_state

fn last_state(self) -> Int

The state of the longest palindromic suffix of the current string; the even root 1 when the string is empty.

  • cost: O(1)
  • ties: None; the longest suffix is unique
  • traps: never

Examples:

  • PalindromicTree<Char>.of("aba").last_state == 4

Source

PalindromicTree.contains

fn contains<S: Seq>(self, word: S) -> Bool

True when word is a palindrome occurring in the pushed string, that is, a state of the tree.

  • cost: O(|word|)
  • empty: true (the even root)
  • traps: never

Examples:

  • let t = PalindromicTree<Char>.of("aba"); t.contains("aba") and not t.contains("ab")

Source

PalindromicTree.min_palindrome_partition

fn min_palindrome_partition(self) -> List<Int>

dp[i] is the least number of palindromes the first i pushed letters split into, for i in 0..=n, by the series-link DP.

  • cost: O(n log n)
  • ties: None; only the count is returned
  • order: keyed by prefix length 0..=n
  • traps: never

Examples:

  • PalindromicTree<Char>.of("aab").min_palindrome_partition() == [0, 1, 1, 2]

Source

Trie

pub struct Trie<A>

Dynamic trie over alphabet domain A. O(|word|) per operation; flat |A|-stride table.

Source

Trie.new

fn new() -> Trie<A>

An empty trie over the alphabet domain A: one root node 0, no words. Call it as Trie<A>(). Nodes are numbered in creation order.

  • cost: O(|A|)
  • traps: never

Examples:

  • Trie<Char>().len == 1

Source

Trie.root

fn root(self) -> Int

The root node, for the empty word: always 0.

  • cost: O(1)
  • traps: never

Examples:

  • Trie<Char>().root == 0

Source

Trie.len

fn len(self) -> Int

The number of nodes, the root included. remove keeps nodes, so this never shrinks except by clear.

  • cost: O(1)
  • traps: never

Examples:

  • var t = Trie<Char>(); t.add("ab"); t.add("ac"); t.len == 4

Source

Trie.is_empty

fn is_empty(self) -> Bool

True when no words are stored (every count is zero), whatever nodes remain.

  • cost: O(1)
  • traps: never

Examples:

  • var t = Trie<Char>(); t.add("a"); t.remove("a"); t.is_empty

Source

Trie.step

fn step(self, node: Int, a: A) -> ?Int

Source

Trie.find

fn find<S: Seq>(self, word: S) -> ?Int

Source

Trie.add

fn add<S: Seq>(mut self, word: S) -> Int

Source

Trie.remove

fn remove<S: Seq>(mut self, word: S) -> Bool

Source

Trie.count

fn count<S: Seq>(self, word: S) -> Int

Source

Trie.count_prefix

fn count_prefix<S: Seq>(self, prefix: S) -> Int

Source

Trie.ends_at

fn ends_at(self, node: Int) -> Int

Source

Trie.pass_at

fn pass_at(self, node: Int) -> Int

Source

Trie.contains

fn contains<S: Seq>(self, word: S) -> Bool

True when at least one copy of exactly word is stored: count(word) > 0.

  • cost: O(|word|)
  • empty: whether the empty word is stored
  • traps: never

Examples:

  • var t = Trie<Char>(); t.add("ab"); t.contains("ab") and not t.contains("a")

Source

Trie.clear

fn clear(mut self)

Removes every word and node, leaving just the root.

  • cost: O(1)
  • traps: never

Examples:

  • var t = Trie<Char>(); t.add("ab"); t.clear(); t.is_empty and t.len == 1

Source

Trie.kth

fn kth(self, k: Int) -> ?List<A>

The k-th (0-based) stored word in lexicographic order, copies counted, as its letters; None when fewer than k + 1 words are stored. A word comes before its extensions.

  • cost: O(depth * |A|)
  • ties: copies of one word are adjacent and interchangeable
  • order: the letters of the word, first to last
  • traps: when k < 0

Examples:

  • var t = Trie<Char>(); t.add("b"); t.add("ab"); t.add("a"); t.kth(1) == Some(['a', 'b']) and t.kth(3) == None

Source

Trie.count_less

fn count_less<S: Seq>(self, word: S) -> Int

The number of stored words (with multiplicity) lexicographically smaller than word.

  • cost: O(|word| * |A|)
  • empty: 0 for an empty word
  • traps: never

Examples:

  • var t = Trie<Char>(); t.add("b"); t.add("ab"); t.add("a"); t.count_less("b") == 2

Source

AhoCorasick

pub struct AhoCorasick<A>

O(total * |A|) build, O(1) step. Aho-Corasick multi-pattern automaton over alphabet domain A. Built in O(sum |p| * |A|) flat memory and time; step, link, and hit are O(1).

Source

AhoCorasick.new

fn new<S: Seq>(patterns: List<S>) -> AhoCorasick<A>

Source

AhoCorasick.root

fn root(self) -> Int

The root state, before any letter is read: always 0.

  • cost: O(1)
  • traps: never

Examples:

  • AhoCorasick<Char>(["a"]).root == 0

Source

AhoCorasick.len

fn len(self) -> Int

The number of states, the root included.

  • cost: O(1)
  • traps: never

Examples:

  • AhoCorasick<Char>(["a", "ab", "b"]).len == 4

Source

AhoCorasick.step

fn step(self, state: Int, a: A) -> Int

Source

fn link(self, state: Int) -> Int

Source

AhoCorasick.hit

fn hit(self, state: Int) -> Bool

Source

AhoCorasick.words_at

fn words_at(self, state: Int) -> List<Int>

Source

AhoCorasick.find_all

fn find_all<S: Seq>(self, text: S) -> yields (at: Int, pattern: Int)

Source

AhoCorasick.counts

fn counts<S: Seq>(self, text: S) -> List<Int>

Source

AhoCorasick.fail_order

fn fail_order(self) -> List<Int>

Every state in BFS order of the trie (root first, then by depth, equal depths by state number), so each state comes after its failure link; iterate backwards for bottom-up DP.

  • cost: O(states)
  • order: non-decreasing depth; ties by smaller state number
  • traps: never

Examples:

  • AhoCorasick<Char>(["a", "ab", "b"]).fail_order() == [0, 1, 3, 2]

Source

fn exit_link(self, state: Int) -> ?Int

The nearest state strictly up the failure links of state at which a pattern ends, or None when there is None.

  • cost: O(1)
  • traps: when state is outside 0..self.len

Examples:

  • let ac = AhoCorasick<Char>(["a", "ab", "b"]); ac.exit_link(2) == Some(3) and ac.exit_link(1) == None

Source

AhoCorasick.pattern_state

fn pattern_state(self, pattern: Int) -> Int

The state where patterns[pattern] ends.

  • cost: O(1)
  • traps: when pattern is outside 0..patterns.len

Examples:

  • AhoCorasick<Char>(["a", "ab", "b"]).pattern_state(1) == 2

Source

DynamicAhoCorasick

pub struct DynamicAhoCorasick<A>

O(|pat| * |A| * log n) amortized insert/delete, O(|text| * log n) query. Online multi-pattern Aho-Corasick via log-decomposed static buckets.

Source

DynamicAhoCorasick.new

fn new() -> DynamicAhoCorasick<A>

An empty online pattern set over the alphabet domain A; call it as DynamicAhoCorasick<A>().

  • cost: O(1)
  • traps: never

Examples:

  • DynamicAhoCorasick<Char>().is_empty

Source

DynamicAhoCorasick.len

fn len(self) -> Int

The number of patterns stored, copies counted.

  • cost: O(1)
  • traps: never

Examples:

  • var d = DynamicAhoCorasick<Char>(); d.add("a"); d.add("a"); d.len == 2

Source

DynamicAhoCorasick.is_empty

fn is_empty(self) -> Bool

True when no patterns are stored.

  • cost: O(1)
  • traps: never

Examples:

  • var d = DynamicAhoCorasick<Char>(); d.add("a"); d.remove("a"); d.is_empty

Source

DynamicAhoCorasick.add

fn add<S: Seq>(mut self, pattern: S)

Stores one more copy of pattern.

  • cost: O(|pattern| * |A| * log n) amortized
  • empty: an empty pattern matches at every at in 0..=|text|
  • traps: when an element of pattern is not in A

Examples:

  • var d = DynamicAhoCorasick<Char>(); d.add("ab"); d.len == 1

Source

DynamicAhoCorasick.remove

fn remove<S: Seq>(mut self, pattern: S)

Removes one stored copy of pattern.

  • cost: O(|pattern| * |A| * log n) amortized
  • empty: removes a copy of the empty pattern
  • traps: when no copy of pattern is stored

Examples:

  • var d = DynamicAhoCorasick<Char>(); d.add("ab"); d.remove("ab"); d.count_matches("ab") == 0

Source

DynamicAhoCorasick.count_matches

fn count_matches<S: Seq>(self, text: S) -> Int

The total number of occurrences of all stored patterns in text, overlaps and copies counted.

  • cost: O(|text| * log n)
  • empty: 0 for an empty text unless an empty pattern is stored
  • traps: when an element of text is not in A

Examples:

  • var d = DynamicAhoCorasick<Char>(); d.add("ab"); d.add("b"); d.count_matches("abb") == 3

Source

On this page

KmpAutomatonKmpAutomaton.newKmpAutomaton.lenKmpAutomaton.stepKmpAutomaton.linkKmpAutomaton.find_allPalindromesPalindromes.lenPalindromes.is_emptyPalindromes.longest_atPalindromes.longest_betweenPalindromes.is_palindromePalindromes.countPalindromes.longestSuffixArraySuffixArray.newSuffixArray.lenSuffixArray.is_emptySuffixArray.lcp_betweenSuffixArray.rank_rangeSuffixArray.find_allSuffixArray.countSuffixArray.lcp_rangeSuffixArray.compareSuffixArray.arg_minSuffixArray.distinctSuffixArray.lcp_of_ranksSuffixArray.splitSuffixArray.kth_distinctSuffixTreeEdgeHashValHashVal.hash_tokenHashableHashable.hash_tokenRollingHashRollingHash.newRollingHash.pushRollingHash.popRollingHash.hash_ofRollingHash.concatRollingHash.lenRollingHash.is_emptyRollingHash.allRollingHash.raw_sliceRollingHash.eq_subRollingHash.sliceRollingHash.getRollingHash.combineRollingHash.lcpRollingHash.lcsRollingHash.lcp_withHash2DHash2D.newHash2D.rectHash61RollingHash61RollingHash61.newRollingHash61.lenRollingHash61.is_emptyRollingHash61.slice61RollingHash61.allRollingHash61.getRollingHash61.combineRollingHash61.pushRollingHash61.popRollingHash61.lcpRollingHash61.lcsRollingHash61.lcp_withDynamicHashDynamicHash.newDynamicHash.lenDynamicHash.is_emptyDynamicHash.allDynamicHash.setDynamicHash.getDynamicHash.rev_getDynamicHash.is_palindromeSuffixAutomatonSuffixAutomaton.newSuffixAutomaton.ofSuffixAutomaton.add_empty_stateSuffixAutomaton.clone_stateSuffixAutomaton.pushSuffixAutomaton.rootSuffixAutomaton.lenSuffixAutomaton.stepSuffixAutomaton.linkSuffixAutomaton.longestSuffixAutomaton.shortestSuffixAutomaton.first_posSuffixAutomaton.findSuffixAutomaton.containsSuffixAutomaton.distinctSuffixAutomaton.topo_orderSuffixAutomaton.occ_countsSuffixAutomaton.lcsSuffixAutomaton.resetSuffixAutomaton.add_wordSuffixAutomaton.statesSuffixAutomaton.endpos_treeSuffixAutomaton.kth_substringPalindromicTreePalindromicTree.newPalindromicTree.ofPalindromicTree.pushPalindromicTree.sizePalindromicTree.atPalindromicTree.growPalindromicTree.lenPalindromicTree.distinctPalindromicTree.pal_lenPalindromicTree.linkPalindromicTree.stepPalindromicTree.diffPalindromicTree.series_linkPalindromicTree.occ_countsPalindromicTree.push_frontPalindromicTree.popPalindromicTree.last_statePalindromicTree.containsPalindromicTree.min_palindrome_partitionTrieTrie.newTrie.rootTrie.lenTrie.is_emptyTrie.stepTrie.findTrie.addTrie.removeTrie.countTrie.count_prefixTrie.ends_atTrie.pass_atTrie.containsTrie.clearTrie.kthTrie.count_lessAhoCorasickAhoCorasick.newAhoCorasick.rootAhoCorasick.lenAhoCorasick.stepAhoCorasick.linkAhoCorasick.hitAhoCorasick.words_atAhoCorasick.find_allAhoCorasick.countsAhoCorasick.fail_orderAhoCorasick.exit_linkAhoCorasick.pattern_stateDynamicAhoCorasickDynamicAhoCorasick.newDynamicAhoCorasick.lenDynamicAhoCorasick.is_emptyDynamicAhoCorasick.addDynamicAhoCorasick.removeDynamicAhoCorasick.count_matches