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.
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
patgives one state,0, which matches everywhere - traps: when an element of
patis not inA
Examples:
KmpAutomaton<Char>("aba").len == 4
KmpAutomaton.len
fn len(self) -> IntThe 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
KmpAutomaton.step
fn step(self, state: Int, a: A) -> IntThe 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
stateis outside0..self.len
Examples:
let k = KmpAutomaton<Char>("aba"); k.step(3, 'b') == 2 and k.step(0, 'b') == 0
KmpAutomaton.link
fn link(self, state: Int) -> IntThe 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
stateis outside0..self.len
Examples:
let k = KmpAutomaton<Char>("aba"); k.link(3) == 1 and k.link(2) == 0
KmpAutomaton.find_all
fn find_all<S: Seq>(self, text: S) -> yields IntThe 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
textyields nothing unlesspatis empty; an emptypatyields0..=|text| - ties: every occurrence is yielded; None is preferred
- order: increasing start
- traps: when an element of
textis not inA
Examples:
KmpAutomaton<Char>("aba").find_all("ababa").collect() == [0, 2]
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].
Palindromes.len
fn len(self) -> IntThe length of the sequence the radii were computed for.
- cost: O(1)
- traps: never
Examples:
manacher("aba").len == 3
Palindromes.is_empty
fn is_empty(self) -> BoolTrue when the sequence the radii were computed for is empty.
- cost: O(1)
- traps: never
Examples:
manacher("").is_empty == true
Palindromes.longest_at
fn longest_at(self, i: Int) -> IntPalindromes.longest_between
fn longest_between(self, i: Int) -> IntPalindromes.is_palindrome
fn is_palindrome<R>(self, r: R) -> BoolTrue 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
rreaches outside0..=self.len
Examples:
let p = manacher("abacaba"); p.is_palindrome(0..3) and not p.is_palindrome(1..4)
Palindromes.count
fn count(self) -> IntThe number of non-empty palindromic substrings, each occurrence counted:
sum(odd) + sum(even).
- cost: O(n)
- traps: never
Examples:
manacher("aaa").count() == 6
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)
SuffixArray
pub struct SuffixArrayO(n) SA-IS + Kasai LCP (O(n log n) with RMQ). Suffix array, inverse rank, adjacent LCP, and O(1) LCP/comparison queries.
SuffixArray.new
fn new<S: Indexed>(s: S) -> SuffixArrayThe 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
Strand small integer alphabets, O(n log n) otherwise - empty:
sa,rankandlcpall empty - traps: never
Examples:
SuffixArray("banana").sa == [5, 3, 1, 0, 4, 2]SuffixArray("banana").lcp == [1, 3, 0, 0, 2]
SuffixArray.len
fn len(self) -> IntThe length n of the sequence the suffix array was built over.
- cost: O(1)
- traps: never
Examples:
SuffixArray("banana").len == 6
SuffixArray.is_empty
fn is_empty(self) -> BoolTrue when the suffix array was built over an empty sequence.
- cost: O(1)
- traps: never
Examples:
SuffixArray("").is_empty == true
SuffixArray.lcp_between
fn lcp_between(self, i: Int, j: Int) -> IntThe 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
iorjis outside0..=self.len
Examples:
SuffixArray("banana").lcp_between(1, 3) == 3
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
patgives0..n - order: a range of ranks, increasing
- traps: never
Examples:
SuffixArray("banana").rank_range("ana") == 1..3SuffixArray("banana").rank_range("c") == 4..4
SuffixArray.find_all
fn find_all<P: Indexed>(self, pat: P) -> yields IntThe start of every occurrence of pat, read off sa over rank_range(pat).
- cost: O(|pat| log n + occurrences)
- empty: an empty
patyields every start0..n(not the end positionn) - 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]
SuffixArray.count
fn count<P: Indexed>(self, pat: P) -> IntThe number of occurrences of pat, overlapping ones included: rank_range(pat).len.
- cost: O(|pat| log n)
- empty: an empty
patgivesn - traps: never
Examples:
SuffixArray("banana").count("an") == 2
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
iis outside0..norlenoutside0..=n - i
Examples:
SuffixArray("banana").lcp_range(1, 3) == 1..3
SuffixArray.compare
fn compare(self, l1: Int, r1: Int, l2: Int, r2: Int) -> IntThe 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..=nor has its end before its start
Examples:
SuffixArray("banana").compare(1, 3, 3, 5) == 0SuffixArray("banana").compare(1, 2, 1, 3) == -1
SuffixArray.arg_min
fn arg_min(self, lo: Int, hi: Int) -> IntSuffixArray.distinct
fn distinct(self) -> IntThe number of distinct non-empty substrings: n * (n + 1) / 2 - sum(lcp).
- cost: O(n)
- traps: never
Examples:
SuffixArray("banana").distinct() == 15
SuffixArray.lcp_of_ranks
fn lcp_of_ranks(self, r: Range<Int>) -> IntThe 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
rtraps - traps: when
ris empty or reaches outside0..n
Examples:
SuffixArray("banana").lcp_of_ranks(1..3) == 3SuffixArray("banana").lcp_of_ranks(3..4) == 6
SuffixArray.split
fn split(self, r: Range<Int>) -> IntWhere 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
rwith fewer than two ranks traps - ties: the smallest such
k - traps: when
r.len < 2orrreaches outside0..n
Examples:
SuffixArray("banana").split(0..3) == 1SuffixArray("banana").split(0..6) == 3
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:
kcounts 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
SuffixTreeEdge
pub struct SuffixTreeEdge(O(1) value. One edge of the compressed suffix tree of a sequence, built in O(n) from SA + LCP.
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).
HashVal.hash_token
fn hash_token(self) -> IntOne 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
Hashable
pub trait HashableO(1) per element. Elements accepted by RollingHash: Char, Int, Bool, HashVal, or any user type
implementing hash_token.
Hashable.hash_token
fn hash_token(self) -> IntRollingHash
pub struct RollingHashO(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.
RollingHash.new
fn new<S: Seq>(seq: S, bases: ?(Int, Int) = None) -> RollingHashRollingHash.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")
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")
RollingHash.hash_of
fn hash_of<S: Seq>(self, seq: S) -> HashValThe 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)
RollingHash.concat
fn concat(self, parts: List<(hash: HashVal, len: Int)>) -> HashValThe 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
lenis negative
Examples:
let h = RollingHash("abcd"); h.concat([(h.get(0..2), 2), (h.get(2..4), 2)]) == h.all
RollingHash.len
fn len(self) -> IntThe number of elements hashed.
- cost: O(1)
- traps: never
Examples:
RollingHash("abc").len == 3
RollingHash.is_empty
fn is_empty(self) -> BoolTrue when no elements are hashed.
- cost: O(1)
- traps: never
Examples:
RollingHash("").is_empty == true
RollingHash.all
fn all(self) -> HashValThe 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)
RollingHash.raw_slice
fn raw_slice(self, l: Int, r: Int) -> HashValRollingHash.eq_sub
fn eq_sub(self, a: Int, b: Int, len: Int) -> BoolRollingHash.slice
fn slice(self, l: Int, r: Int) -> HashValThe hash of the half-open slice l..r (0-based); HashVal(0, 0) when l == r.
- cost: O(1)
- traps: when
l > r,l < 0orr > self.len
Examples:
let h = RollingHash("abab"); h.slice(0, 2) == h.slice(2, 4) and h.slice(1, 1) == HashVal(0, 0)
RollingHash.get
fn get<R>(self, r: R) -> HashValThe 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)
RollingHash.combine
fn combine(self, a: HashVal, b: HashVal, b_len: Int) -> HashValThe 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
lenon demand) - traps: when
b_len < 0
Examples:
let h = RollingHash("abc"); h.combine(h.get(0..1), h.get(1..3), 2) == h.all
RollingHash.lcp
fn lcp(self, a: Int, b: Int) -> IntThe 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
aorbis outside0..=self.len
Examples:
RollingHash("abcabd").lcp(0, 3) == 2
RollingHash.lcs
fn lcs(self, a: Int, b: Int) -> IntThe 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
aorbis outside0..=self.len
Examples:
RollingHash("xabyab").lcs(3, 6) == 2
RollingHash.lcp_with
fn lcp_with(self, a: Int, other: RollingHash, b: Int) -> IntThe 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,
ais outside0..=self.lenorboutside0..=other.len
Examples:
RollingHash("abcd", bases: Some((131, 137))).lcp_with(1, RollingHash("xbcx", bases: Some((131, 137))), 1) == 2
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.
Hash2D.new
fn new(code: (R, C) -> Int, bases: ?(Int, Int) = None) -> Hash2D<R, C>Hash2D.rect
fn rect(self, rows: Range<R>, cols: Range<C>) -> HashValHash61
pub struct Hash61(vO(1) value. Single-modulus 2^61 - 1 (Mersenne prime) polynomial hash value (Copy + Eq + Ord + Hash).
RollingHash61
pub struct RollingHash61O(n) build, O(1) query. Single-modulus 2^61 - 1 polynomial rolling hash with randomized base.
RollingHash61.new
fn new<S: Seq>(seq: S, base: ?U64 = None) -> RollingHash61A 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;
pushcan 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)
RollingHash61.len
fn len(self) -> IntThe number of elements hashed.
- cost: O(1)
- traps: never
Examples:
RollingHash61("abc").len == 3
RollingHash61.is_empty
fn is_empty(self) -> BoolTrue when no elements are hashed.
- cost: O(1)
- traps: never
Examples:
RollingHash61("").is_empty == true
RollingHash61.slice61
fn slice61(self, l: Int, r: Int) -> Hash61RollingHash61.all
fn all(self) -> Hash61The 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)
RollingHash61.get
fn get<R>(self, r: R) -> Hash61The 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)
RollingHash61.combine
fn combine(self, a: Hash61, b: Hash61, b_len: Int) -> Hash61The 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
lenon demand) - traps: when
b_len < 0
Examples:
let h = RollingHash61("abc"); h.combine(h.get(0..1), h.get(1..3), 2) == h.all
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)
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
RollingHash61.lcp
fn lcp(self, a: Int, b: Int) -> IntThe 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
aorbis outside0..=self.len
Examples:
RollingHash61("abcabd").lcp(0, 3) == 2
RollingHash61.lcs
fn lcs(self, a: Int, b: Int) -> IntThe 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
aorbis outside0..=self.len
Examples:
RollingHash61("xabyab").lcs(3, 6) == 2
RollingHash61.lcp_with
fn lcp_with(self, a: Int, other: RollingHash61, b: Int) -> IntThe 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,
ais outside0..=self.lenorboutside0..=other.len
Examples:
RollingHash61("abcd", base: Some(U64(131))).lcp_with(1, RollingHash61("xbcx", base: Some(U64(131))), 1) == 2
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.
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)
DynamicHash.len
fn len(self) -> IntThe number of hashed positions, D.K.
- cost: O(1)
- traps: never
Examples:
DynamicHash("abc").len == 3
DynamicHash.is_empty
fn is_empty(self) -> BoolTrue when there are no positions.
- cost: O(1)
- traps: never
Examples:
DynamicHash("").is_empty == true
DynamicHash.all
fn all(self) -> HashValThe hash of the whole sequence, self.get(..).
- cost: O(1)
- traps: never
Examples:
let h = DynamicHash("abab"); h.all == h.get(0..4)
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 (
iis aD)
Examples:
var h = DynamicHash("abxb"); h.set(2, 'a'); h.get(0..2) == h.get(2..4)
DynamicHash.get
fn get(self, r: Range<D>) -> HashValThe hash of the elements over r in order (a cut range j..i works too, decision 124).
- cost: O(log n)
- empty: an empty
rgivesHashVal(0, 0) - traps: never (
ris aRange<D>)
Examples:
let h = DynamicHash("xyxy"); h.get(0..2) == h.get(2..4)
DynamicHash.rev_get
fn rev_get(self, r: Range<D>) -> HashValThe hash of the elements over r read backwards, comparable with get.
- cost: O(log n)
- empty: an empty
rgivesHashVal(0, 0) - traps: never (
ris aRange<D>)
Examples:
let h = DynamicHash("abba"); h.rev_get(0..2) == h.get(2..4)
DynamicHash.is_palindrome
fn is_palindrome(self, r: Range<D>) -> BoolTrue when the elements over r read the same both ways: get(r) == rev_get(r).
- cost: O(log n)
- empty:
truefor an emptyr - traps: never (
ris aRange<D>)
Examples:
let h = DynamicHash("abca"); h.is_palindrome(1..2) and not h.is_palindrome(0..4)
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.
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
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
sis not inA
Examples:
SuffixAutomaton<Char>.of("abb").len == 5
SuffixAutomaton.add_empty_state
fn add_empty_state(mut self, length: Int, is_prefix: Bool) -> IntSuffixAutomaton.clone_state
fn clone_state(mut self, src: Int, length: Int) -> IntSuffixAutomaton.push
fn push(mut self, a: A)SuffixAutomaton.root
fn root(self) -> IntThe root state, for the empty string: always 0.
- cost: O(1)
- traps: never
Examples:
SuffixAutomaton<Char>.of("ab").root == 0
SuffixAutomaton.len
fn len(self) -> IntThe number of states, the root included; at most max(1, 2n - 1).
- cost: O(1)
- traps: never
Examples:
SuffixAutomaton<Char>.of("abb").len == 5
SuffixAutomaton.step
fn step(self, state: Int, a: A) -> ?IntSuffixAutomaton.link
fn link(self, state: Int) -> ?IntSuffixAutomaton.longest
fn longest(self, state: Int) -> IntSuffixAutomaton.shortest
fn shortest( self, state: Int, ) -> IntSuffixAutomaton.first_pos
fn first_pos(self, state: Int) -> IntSuffixAutomaton.find
fn find<S: Seq>(self, word: S) -> ?IntSuffixAutomaton.contains
fn contains<S: Seq>(self, word: S) -> BoolTrue when word is a substring of the automaton's string: find(word) != None.
- cost: O(|word|)
- empty:
truefor an emptyword - traps: when an element of
wordis not inA
Examples:
let m = SuffixAutomaton<Char>.of("abb"); m.contains("ab") and not m.contains("ba")
SuffixAutomaton.distinct
fn distinct(self) -> IntThe 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
SuffixAutomaton.topo_order
fn topo_order(self) -> List<Int>SuffixAutomaton.occ_counts
fn occ_counts(self) -> List<Int>SuffixAutomaton.lcs
fn lcs<S: Seq>(self, other: S) -> (len: Int, end: Int)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")
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
wordonly resets - traps: when an element of
wordis not inA
Examples:
var m = SuffixAutomaton<Char>(); m.add_word("ab"); m.add_word("b"); m.distinct() == 3
SuffixAutomaton.states
fn states(self) -> yields IntEvery 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]
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]]
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'])
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).
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
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
sis not inA
Examples:
PalindromicTree<Char>.of("aba").distinct == 3
PalindromicTree.push
fn push(mut self, a: A) -> IntPalindromicTree.size
fn size(self) -> IntPalindromicTree.at
fn at(self, i: Int) -> APalindromicTree.grow
fn grow(mut self, cur: Int, c: Int, link_to: Int)PalindromicTree.len
fn len(self) -> IntThe number of states, both roots included: distinct + 2.
- cost: O(1)
- traps: never
Examples:
PalindromicTree<Char>.of("aba").len == 5
PalindromicTree.distinct
fn distinct(self) -> IntThe number of distinct non-empty palindromic substrings, len - 2; at most n.
- cost: O(1)
- traps: never
Examples:
PalindromicTree<Char>.of("aba").distinct == 3
PalindromicTree.pal_len
fn pal_len(self, state: Int) -> IntPalindromicTree.link
fn link(self, state: Int) -> IntPalindromicTree.step
fn step(self, state: Int, a: A) -> ?IntPalindromicTree.diff
fn diff(self, state: Int) -> IntPalindromicTree.series_link
fn series_link(self, state: Int) -> IntPalindromicTree.occ_counts
fn occ_counts(self) -> List<Int>PalindromicTree.push_front
fn push_front(mut self, a: A) -> IntPrepends 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 (
ais anA)
Examples:
var t = PalindromicTree<Char>.of("ba"); t.push_front('a') == 4
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
pushto undo
Examples:
var t = PalindromicTree<Char>.of("ab"); t.pop(); t.distinct == 1 and t.last_state == 2
PalindromicTree.last_state
fn last_state(self) -> IntThe 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
PalindromicTree.contains
fn contains<S: Seq>(self, word: S) -> BoolTrue 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")
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]
Trie
pub struct Trie<A>Dynamic trie over alphabet domain A. O(|word|) per operation; flat |A|-stride table.
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
Trie.root
fn root(self) -> IntThe root node, for the empty word: always 0.
- cost: O(1)
- traps: never
Examples:
Trie<Char>().root == 0
Trie.len
fn len(self) -> IntThe 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
Trie.is_empty
fn is_empty(self) -> BoolTrue 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
Trie.step
fn step(self, node: Int, a: A) -> ?IntTrie.find
fn find<S: Seq>(self, word: S) -> ?IntTrie.add
fn add<S: Seq>(mut self, word: S) -> IntTrie.remove
fn remove<S: Seq>(mut self, word: S) -> BoolTrie.count
fn count<S: Seq>(self, word: S) -> IntTrie.count_prefix
fn count_prefix<S: Seq>(self, prefix: S) -> IntTrie.ends_at
fn ends_at(self, node: Int) -> IntTrie.pass_at
fn pass_at(self, node: Int) -> IntTrie.contains
fn contains<S: Seq>(self, word: S) -> BoolTrue 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")
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
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
Trie.count_less
fn count_less<S: Seq>(self, word: S) -> IntThe number of stored words (with multiplicity) lexicographically smaller than word.
- cost: O(|word| * |A|)
- empty:
0for an emptyword - traps: never
Examples:
var t = Trie<Char>(); t.add("b"); t.add("ab"); t.add("a"); t.count_less("b") == 2
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).
AhoCorasick.new
fn new<S: Seq>(patterns: List<S>) -> AhoCorasick<A>AhoCorasick.root
fn root(self) -> IntThe root state, before any letter is read: always 0.
- cost: O(1)
- traps: never
Examples:
AhoCorasick<Char>(["a"]).root == 0
AhoCorasick.len
fn len(self) -> IntThe number of states, the root included.
- cost: O(1)
- traps: never
Examples:
AhoCorasick<Char>(["a", "ab", "b"]).len == 4
AhoCorasick.step
fn step(self, state: Int, a: A) -> IntAhoCorasick.link
fn link(self, state: Int) -> IntAhoCorasick.hit
fn hit(self, state: Int) -> BoolAhoCorasick.words_at
fn words_at(self, state: Int) -> List<Int>AhoCorasick.find_all
fn find_all<S: Seq>(self, text: S) -> yields (at: Int, pattern: Int)AhoCorasick.counts
fn counts<S: Seq>(self, text: S) -> List<Int>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]
AhoCorasick.exit_link
fn exit_link(self, state: Int) -> ?IntThe 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
stateis outside0..self.len
Examples:
let ac = AhoCorasick<Char>(["a", "ab", "b"]); ac.exit_link(2) == Some(3) and ac.exit_link(1) == None
AhoCorasick.pattern_state
fn pattern_state(self, pattern: Int) -> IntThe state where patterns[pattern] ends.
- cost: O(1)
- traps: when
patternis outside0..patterns.len
Examples:
AhoCorasick<Char>(["a", "ab", "b"]).pattern_state(1) == 2
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.
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
DynamicAhoCorasick.len
fn len(self) -> IntThe 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
DynamicAhoCorasick.is_empty
fn is_empty(self) -> BoolTrue when no patterns are stored.
- cost: O(1)
- traps: never
Examples:
var d = DynamicAhoCorasick<Char>(); d.add("a"); d.remove("a"); d.is_empty
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
atin0..=|text| - traps: when an element of
patternis not inA
Examples:
var d = DynamicAhoCorasick<Char>(); d.add("ab"); d.len == 1
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
patternis stored
Examples:
var d = DynamicAhoCorasick<Char>(); d.add("ab"); d.remove("ab"); d.count_matches("ab") == 0
DynamicAhoCorasick.count_matches
fn count_matches<S: Seq>(self, text: S) -> IntThe total number of occurrences of all stored patterns in text, overlaps and copies
counted.
- cost: O(|text| * log n)
- empty:
0for an emptytextunless an empty pattern is stored - traps: when an element of
textis not inA
Examples:
var d = DynamicAhoCorasick<Char>(); d.add("ab"); d.add("b"); d.count_matches("abb") == 3