pub fn new(text: impl IntoIterator<Item = u8>) -> Self {
        let init_rank = text.into_iter().map(|ch| ch as usize).collect::<Vec<_>>();
        let n = init_rank.len();
        let mut sfx = Self::counting_sort(0..n, &init_rank, 256);
        let mut rank = vec![init_rank];
        // Invariant at the start of every loop iteration:
        // suffixes are sorted according to the first skip characters.
        for skip in (0..).map(|i| 1 << i).take_while(|&skip| skip < n) {
            let prev_rank = rank.last().unwrap();
            let mut cur_rank = prev_rank.clone();

            let pos = (n - skip..n).chain(sfx.into_iter().filter_map(|p| p.checked_sub(skip)));
            sfx = Self::counting_sort(pos, &prev_rank, max(n, 256));

            let mut prev = sfx[0];
            cur_rank[prev] = 0;
            for &cur in sfx.iter().skip(1) {
                if max(prev, cur) + skip < n
                    && prev_rank[prev] == prev_rank[cur]
                    && prev_rank[prev + skip] == prev_rank[cur + skip]
                {
                    cur_rank[cur] = cur_rank[prev];
                } else {
                    cur_rank[cur] = cur_rank[prev] + 1;
                }
                prev = cur;
            }
            rank.push(cur_rank);
        }
        Self { sfx, rank }
    }
/// Suffix array construction in O(n log n) time.
Suffix array construction in O(n log n) time.
Suffix array construction in O ( n log n ) time .
pub fn new(text: impl IntoIterator<Item = u8>) -> Self {
        let init_rank = text.into_iter().map(|ch| ch as usize).collect::<Vec<_>>();
        let n = init_rank.len();
        let mut sfx = Self::counting_sort(0..n, &init_rank, 256);
        let mut rank = vec![init_rank];
        // Invariant at the start of every loop iteration:
        // suffixes are sorted according to the first skip characters.
        for skip in (0..).map(|i| 1 << i).take_while(|&skip| skip < n) {
            let prev_rank = rank.last().unwrap();
            let mut cur_rank = prev_rank.clone();
            let pos = (n - skip..n).chain(sfx.into_iter().filter_map(|p| p.checked_sub(skip)));
            sfx = Self::counting_sort(pos, &prev_rank, max(n, 256));
            let mut prev = sfx[0];
            cur_rank[prev] = 0;
            for &cur in sfx.iter().skip(1) {
                if max(prev, cur) + skip < n
                    && prev_rank[prev] == prev_rank[cur]
                    && prev_rank[prev + skip] == prev_rank[cur + skip]
                {
                    cur_rank[cur] = cur_rank[prev];
                } else {
                    cur_rank[cur] = cur_rank[prev] + 1;
                }
                prev = cur;
            }
            rank.push(cur_rank);
        }
        Self { sfx, rank }
    }
pub fn new ( text : impl IntoIterator < Item = u8 > ) -> Self { let init_rank = text . into_iter ( ) . map ( | ch | ch as usize ) . collect :: < Vec < _ > > ( ) ; let n = init_rank . len ( ) ; let mut sfx = Self :: counting_sort ( 0 .. n , & init_rank , 256 ) ; let mut rank = vec ! [ init_rank ] ; // Invariant at the start of every loop iteration: // suffixes are sorted according to the first skip characters. for skip in ( 0 .. ) . map ( | i | 1 << i ) . take_while ( | & skip | skip < n ) { let prev_rank = rank . last ( ) . unwrap ( ) ; let mut cur_rank = prev_rank . clone ( ) ; let pos = ( n - skip .. n ) . chain ( sfx . into_iter ( ) . filter_map ( | p | p . checked_sub ( skip ) ) ) ; sfx = Self :: counting_sort ( pos , & prev_rank , max ( n , 256 ) ) ; let mut prev = sfx [ 0 ] ; cur_rank [ prev ] = 0 ; for & cur in sfx . iter ( ) . skip ( 1 ) { if max ( prev , cur ) + skip < n && prev_rank [ prev ] == prev_rank [ cur ] && prev_rank [ prev + skip ] == prev_rank [ cur + skip ] { cur_rank [ cur ] = cur_rank [ prev ] ; } else { cur_rank [ cur ] = cur_rank [ prev ] + 1 ; } prev = cur ; } rank . push ( cur_rank ) ; } Self { sfx , rank } }
Suffix array construction in O(n log n) time.
Suffix array construction in O ( n log n ) time .
text
impl IntoIterator<Item = u8>