Skip to main content

SuffixTreeBuilder

competitive::string::suffix_tree

Struct SuffixTreeBuilder 

Source 
struct SuffixTreeBuilder {
    nodes: Vec<STNode>,
    links: Vec<Link>,
}

Fields§

§nodes: Vec<STNode>§links: Vec<Link>

Implementations§

Source§

impl SuffixTreeBuilder

Source

fn with_capacity(capacity: usize) -> Self

Examples found in repository?
crates/competitive/src/string/suffix_tree.rs (line 205)
201    pub fn new(text: Vec<T>) -> Self {
202        let n = text.len();
203        let suffix_array = SuffixArray::new(&text);
204        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
205        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
206        builder.push_node(0, 0);
207        let mut leafs = vec![!0; n + 1];
208        leafs[0] = 0;
209        let mut stack = Vec::with_capacity(n);
210        stack.push(0);
211        for i in 1..=n {
212            let lcp = lcp_array[i - 1];
213            let mut last_popped = !0;
214            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
215                last_popped = stack.pop().unwrap();
216                builder.nodes[last_popped].sa_range.end = i;
217            }
218
219            // internal node
220            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
221                let parent = stack.last().cloned().unwrap();
222                let internal = builder.nodes.len();
223                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
224                builder.detach_last_child(parent, last_popped);
225                builder.attach_child(parent, internal);
226                builder.attach_child(internal, last_popped);
227                stack.push(internal);
228            }
229
230            // leaf node
231            let parent = stack.last().cloned().unwrap();
232            let leaf = builder.nodes.len();
233            builder.push_node(n - suffix_array[i], i);
234            builder.attach_child(parent, leaf);
235            stack.push(leaf);
236            leafs[i] = leaf;
237        }
238        while let Some(node) = stack.pop() {
239            builder.nodes[node].sa_range.end = n + 1;
240        }
241
242        builder.reindex(&mut leafs[1..]);
243        let children = builder.build_children();
244        let inv = builder.build_aux(&children);
245        let nodes = builder.nodes;
246        let suffix_array = suffix_array.into_inner();
247
248        Self {
249            text,
250            suffix_array,
251            lcp_array,
252            rank,
253            nodes,
254            children,
255            leafs,
256            inv,
257        }
258    }
Source

fn push_node(&mut self, depth: usize, start: usize) -> usize

Examples found in repository?
crates/competitive/src/string/suffix_tree.rs (line 206)
201    pub fn new(text: Vec<T>) -> Self {
202        let n = text.len();
203        let suffix_array = SuffixArray::new(&text);
204        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
205        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
206        builder.push_node(0, 0);
207        let mut leafs = vec![!0; n + 1];
208        leafs[0] = 0;
209        let mut stack = Vec::with_capacity(n);
210        stack.push(0);
211        for i in 1..=n {
212            let lcp = lcp_array[i - 1];
213            let mut last_popped = !0;
214            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
215                last_popped = stack.pop().unwrap();
216                builder.nodes[last_popped].sa_range.end = i;
217            }
218
219            // internal node
220            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
221                let parent = stack.last().cloned().unwrap();
222                let internal = builder.nodes.len();
223                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
224                builder.detach_last_child(parent, last_popped);
225                builder.attach_child(parent, internal);
226                builder.attach_child(internal, last_popped);
227                stack.push(internal);
228            }
229
230            // leaf node
231            let parent = stack.last().cloned().unwrap();
232            let leaf = builder.nodes.len();
233            builder.push_node(n - suffix_array[i], i);
234            builder.attach_child(parent, leaf);
235            stack.push(leaf);
236            leafs[i] = leaf;
237        }
238        while let Some(node) = stack.pop() {
239            builder.nodes[node].sa_range.end = n + 1;
240        }
241
242        builder.reindex(&mut leafs[1..]);
243        let children = builder.build_children();
244        let inv = builder.build_aux(&children);
245        let nodes = builder.nodes;
246        let suffix_array = suffix_array.into_inner();
247
248        Self {
249            text,
250            suffix_array,
251            lcp_array,
252            rank,
253            nodes,
254            children,
255            leafs,
256            inv,
257        }
258    }
Source

fn attach_child(&mut self, parent: usize, child: usize)

Examples found in repository?
crates/competitive/src/string/suffix_tree.rs (line 225)
201    pub fn new(text: Vec<T>) -> Self {
202        let n = text.len();
203        let suffix_array = SuffixArray::new(&text);
204        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
205        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
206        builder.push_node(0, 0);
207        let mut leafs = vec![!0; n + 1];
208        leafs[0] = 0;
209        let mut stack = Vec::with_capacity(n);
210        stack.push(0);
211        for i in 1..=n {
212            let lcp = lcp_array[i - 1];
213            let mut last_popped = !0;
214            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
215                last_popped = stack.pop().unwrap();
216                builder.nodes[last_popped].sa_range.end = i;
217            }
218
219            // internal node
220            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
221                let parent = stack.last().cloned().unwrap();
222                let internal = builder.nodes.len();
223                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
224                builder.detach_last_child(parent, last_popped);
225                builder.attach_child(parent, internal);
226                builder.attach_child(internal, last_popped);
227                stack.push(internal);
228            }
229
230            // leaf node
231            let parent = stack.last().cloned().unwrap();
232            let leaf = builder.nodes.len();
233            builder.push_node(n - suffix_array[i], i);
234            builder.attach_child(parent, leaf);
235            stack.push(leaf);
236            leafs[i] = leaf;
237        }
238        while let Some(node) = stack.pop() {
239            builder.nodes[node].sa_range.end = n + 1;
240        }
241
242        builder.reindex(&mut leafs[1..]);
243        let children = builder.build_children();
244        let inv = builder.build_aux(&children);
245        let nodes = builder.nodes;
246        let suffix_array = suffix_array.into_inner();
247
248        Self {
249            text,
250            suffix_array,
251            lcp_array,
252            rank,
253            nodes,
254            children,
255            leafs,
256            inv,
257        }
258    }
Source

fn detach_last_child(&mut self, parent: usize, child: usize)

Examples found in repository?
crates/competitive/src/string/suffix_tree.rs (line 224)
201    pub fn new(text: Vec<T>) -> Self {
202        let n = text.len();
203        let suffix_array = SuffixArray::new(&text);
204        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
205        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
206        builder.push_node(0, 0);
207        let mut leafs = vec![!0; n + 1];
208        leafs[0] = 0;
209        let mut stack = Vec::with_capacity(n);
210        stack.push(0);
211        for i in 1..=n {
212            let lcp = lcp_array[i - 1];
213            let mut last_popped = !0;
214            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
215                last_popped = stack.pop().unwrap();
216                builder.nodes[last_popped].sa_range.end = i;
217            }
218
219            // internal node
220            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
221                let parent = stack.last().cloned().unwrap();
222                let internal = builder.nodes.len();
223                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
224                builder.detach_last_child(parent, last_popped);
225                builder.attach_child(parent, internal);
226                builder.attach_child(internal, last_popped);
227                stack.push(internal);
228            }
229
230            // leaf node
231            let parent = stack.last().cloned().unwrap();
232            let leaf = builder.nodes.len();
233            builder.push_node(n - suffix_array[i], i);
234            builder.attach_child(parent, leaf);
235            stack.push(leaf);
236            leafs[i] = leaf;
237        }
238        while let Some(node) = stack.pop() {
239            builder.nodes[node].sa_range.end = n + 1;
240        }
241
242        builder.reindex(&mut leafs[1..]);
243        let children = builder.build_children();
244        let inv = builder.build_aux(&children);
245        let nodes = builder.nodes;
246        let suffix_array = suffix_array.into_inner();
247
248        Self {
249            text,
250            suffix_array,
251            lcp_array,
252            rank,
253            nodes,
254            children,
255            leafs,
256            inv,
257        }
258    }
Source

fn reindex(&mut self, leafs: &mut [usize])

Examples found in repository?
crates/competitive/src/string/suffix_tree.rs (line 242)
201    pub fn new(text: Vec<T>) -> Self {
202        let n = text.len();
203        let suffix_array = SuffixArray::new(&text);
204        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
205        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
206        builder.push_node(0, 0);
207        let mut leafs = vec![!0; n + 1];
208        leafs[0] = 0;
209        let mut stack = Vec::with_capacity(n);
210        stack.push(0);
211        for i in 1..=n {
212            let lcp = lcp_array[i - 1];
213            let mut last_popped = !0;
214            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
215                last_popped = stack.pop().unwrap();
216                builder.nodes[last_popped].sa_range.end = i;
217            }
218
219            // internal node
220            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
221                let parent = stack.last().cloned().unwrap();
222                let internal = builder.nodes.len();
223                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
224                builder.detach_last_child(parent, last_popped);
225                builder.attach_child(parent, internal);
226                builder.attach_child(internal, last_popped);
227                stack.push(internal);
228            }
229
230            // leaf node
231            let parent = stack.last().cloned().unwrap();
232            let leaf = builder.nodes.len();
233            builder.push_node(n - suffix_array[i], i);
234            builder.attach_child(parent, leaf);
235            stack.push(leaf);
236            leafs[i] = leaf;
237        }
238        while let Some(node) = stack.pop() {
239            builder.nodes[node].sa_range.end = n + 1;
240        }
241
242        builder.reindex(&mut leafs[1..]);
243        let children = builder.build_children();
244        let inv = builder.build_aux(&children);
245        let nodes = builder.nodes;
246        let suffix_array = suffix_array.into_inner();
247
248        Self {
249            text,
250            suffix_array,
251            lcp_array,
252            rank,
253            nodes,
254            children,
255            leafs,
256            inv,
257        }
258    }
Source

fn build_aux(&mut self, children: &[usize]) -> Vec<usize>

Examples found in repository?
crates/competitive/src/string/suffix_tree.rs (line 244)
201    pub fn new(text: Vec<T>) -> Self {
202        let n = text.len();
203        let suffix_array = SuffixArray::new(&text);
204        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
205        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
206        builder.push_node(0, 0);
207        let mut leafs = vec![!0; n + 1];
208        leafs[0] = 0;
209        let mut stack = Vec::with_capacity(n);
210        stack.push(0);
211        for i in 1..=n {
212            let lcp = lcp_array[i - 1];
213            let mut last_popped = !0;
214            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
215                last_popped = stack.pop().unwrap();
216                builder.nodes[last_popped].sa_range.end = i;
217            }
218
219            // internal node
220            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
221                let parent = stack.last().cloned().unwrap();
222                let internal = builder.nodes.len();
223                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
224                builder.detach_last_child(parent, last_popped);
225                builder.attach_child(parent, internal);
226                builder.attach_child(internal, last_popped);
227                stack.push(internal);
228            }
229
230            // leaf node
231            let parent = stack.last().cloned().unwrap();
232            let leaf = builder.nodes.len();
233            builder.push_node(n - suffix_array[i], i);
234            builder.attach_child(parent, leaf);
235            stack.push(leaf);
236            leafs[i] = leaf;
237        }
238        while let Some(node) = stack.pop() {
239            builder.nodes[node].sa_range.end = n + 1;
240        }
241
242        builder.reindex(&mut leafs[1..]);
243        let children = builder.build_children();
244        let inv = builder.build_aux(&children);
245        let nodes = builder.nodes;
246        let suffix_array = suffix_array.into_inner();
247
248        Self {
249            text,
250            suffix_array,
251            lcp_array,
252            rank,
253            nodes,
254            children,
255            leafs,
256            inv,
257        }
258    }
Source

fn build_children(&mut self) -> Vec<usize>

Examples found in repository?
crates/competitive/src/string/suffix_tree.rs (line 243)
201    pub fn new(text: Vec<T>) -> Self {
202        let n = text.len();
203        let suffix_array = SuffixArray::new(&text);
204        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
205        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
206        builder.push_node(0, 0);
207        let mut leafs = vec![!0; n + 1];
208        leafs[0] = 0;
209        let mut stack = Vec::with_capacity(n);
210        stack.push(0);
211        for i in 1..=n {
212            let lcp = lcp_array[i - 1];
213            let mut last_popped = !0;
214            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
215                last_popped = stack.pop().unwrap();
216                builder.nodes[last_popped].sa_range.end = i;
217            }
218
219            // internal node
220            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
221                let parent = stack.last().cloned().unwrap();
222                let internal = builder.nodes.len();
223                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
224                builder.detach_last_child(parent, last_popped);
225                builder.attach_child(parent, internal);
226                builder.attach_child(internal, last_popped);
227                stack.push(internal);
228            }
229
230            // leaf node
231            let parent = stack.last().cloned().unwrap();
232            let leaf = builder.nodes.len();
233            builder.push_node(n - suffix_array[i], i);
234            builder.attach_child(parent, leaf);
235            stack.push(leaf);
236            leafs[i] = leaf;
237        }
238        while let Some(node) = stack.pop() {
239            builder.nodes[node].sa_range.end = n + 1;
240        }
241
242        builder.reindex(&mut leafs[1..]);
243        let children = builder.build_children();
244        let inv = builder.build_aux(&children);
245        let nodes = builder.nodes;
246        let suffix_array = suffix_array.into_inner();
247
248        Self {
249            text,
250            suffix_array,
251            lcp_array,
252            rank,
253            nodes,
254            children,
255            leafs,
256            inv,
257        }
258    }

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.