/// Find supermaximal exact matches (of length >= l) of given pattern that overlap position i in the pattern.
/// Complexity O(m) with pattern of length m.
///
/// # Example
///
/// ```
/// use bio::alphabets::dna;
/// use bio::data_structures::bwt::{bwt, less, Occ};
/// use bio::data_structures::fmindex::{FMDIndex, FMIndex};
/// use bio::data_structures::suffix_array::suffix_array;
///
/// let text = b"ATTC$GAAT$";
/// let alphabet = dna::n_alphabet();
/// let sa = suffix_array(text);
/// let bwt = bwt(text, &sa);
/// let less = less(&bwt, &alphabet);
/// let occ = Occ::new(&bwt, 3, &alphabet);
/// let fm = FMIndex::new(&bwt, &less, &occ);
/// let fmdindex = FMDIndex::from(fm);
///
/// let pattern = b"ATT";
/// let intervals = fmdindex.smems(pattern, 2, 0);
///
/// let forward_positions = intervals[0].0.forward().occ(&sa);
/// let revcomp_positions = intervals[0].0.revcomp().occ(&sa);
/// let pattern_position = intervals[0].1;
/// let smem_len = intervals[0].2;
///
/// assert_eq!(forward_positions, [0]);
/// assert_eq!(revcomp_positions, [6]);
/// assert_eq!(pattern_position, 0);
/// assert_eq!(smem_len, 3);
/// ```
Find supermaximal exact matches (of length >= l) of given pattern that overlap position i in the pattern.
Complexity O(m) with pattern of length m.
Find supermaximal exact matches ( of length > = l ) of given pattern that overlap position i in the pattern . Complexity O ( m ) with pattern of length m .
pub fn smems(&self, pattern: &[u8], i: usize, l: usize) -> Vec<(BiInterval, usize, usize)> {
        let curr = &mut Vec::new(); // pairs (biinterval, current match length)
        let prev = &mut Vec::new(); // """
        let mut matches = Vec::new(); // triples (biinterval, position on pattern, smem length)
        let mut match_len = 0;
        let mut interval = self.init_interval_with(pattern[i]);
        if interval.size != 0 {
            match_len += 1;
        }
        for &a in pattern[i + 1..].iter() {
            // forward extend interval
            let forward_interval = self.forward_ext(&interval, a);
            // if size changed, add last interval to list
            if interval.size != forward_interval.size {
                curr.push((interval, match_len));
            }
            // if new interval size is zero, stop, as no further forward extension is possible
            if forward_interval.size == 0 {
                break;
            }
            interval = forward_interval;
            match_len += 1;
        }
        // add the last non-zero interval
        curr.push((interval, match_len));
        // reverse intervals such that longest comes first
        curr.reverse();
        swap(curr, prev);
        let mut j = pattern.len() as isize;
        for k in (-1..i as isize).rev() {
            let a = if k == -1 { b'$' } else { pattern[k as usize] };
            curr.clear();
            // size of the last confirmed interval
            let mut last_size = -1;
            for (interval, match_len) in prev.iter() {
                // backward extend interval
                let forward_interval = self.backward_ext(interval, a);
                if (forward_interval.size == 0 || k == -1) &&
                        // interval could not be extended further
                        // if no interval has been extended this iteration,
                        // interval is maximal and can be added to the matches
                        curr.is_empty() && k < j &&
                        match_len >= &l
                {
                    j = k;
                    matches.push((*interval, (k + 1) as usize, *match_len));
                }
                // add _interval to curr (will be further extended next iteration)
                if forward_interval.size != 0 && forward_interval.size as isize != last_size {
                    last_size = forward_interval.size as isize;
                    curr.push((forward_interval, match_len + 1));
                }
            }
            if curr.is_empty() {
                break;
            }
            swap(curr, prev);
        }
        matches
    }
pub fn smems ( & self , pattern : & [ u8 ] , i : usize , l : usize ) -> Vec < ( BiInterval , usize , usize ) > { let curr = & mut Vec :: new ( ) ; // pairs (biinterval, current match length) let prev = & mut Vec :: new ( ) ; // """ let mut matches = Vec :: new ( ) ; // triples (biinterval, position on pattern, smem length) let mut match_len = 0 ; let mut interval = self . init_interval_with ( pattern [ i ] ) ; if interval . size != 0 { match_len += 1 ; } for & a in pattern [ i + 1 .. ] . iter ( ) { // forward extend interval let forward_interval = self . forward_ext ( & interval , a ) ; // if size changed, add last interval to list if interval . size != forward_interval . size { curr . push ( ( interval , match_len ) ) ; } // if new interval size is zero, stop, as no further forward extension is possible if forward_interval . size == 0 { break ; } interval = forward_interval ; match_len += 1 ; } // add the last non-zero interval curr . push ( ( interval , match_len ) ) ; // reverse intervals such that longest comes first curr . reverse ( ) ; swap ( curr , prev ) ; let mut j = pattern . len ( ) as isize ; for k in ( - 1 .. i as isize ) . rev ( ) { let a = if k == - 1 { b'$' } else { pattern [ k as usize ] } ; curr . clear ( ) ; // size of the last confirmed interval let mut last_size = - 1 ; for ( interval , match_len ) in prev . iter ( ) { // backward extend interval let forward_interval = self . backward_ext ( interval , a ) ; if ( forward_interval . size == 0 || k == - 1 ) && // interval could not be extended further // if no interval has been extended this iteration, // interval is maximal and can be added to the matches curr . is_empty ( ) && k < j && match_len >= & l { j = k ; matches . push ( ( * interval , ( k + 1 ) as usize , * match_len ) ) ; } // add _interval to curr (will be further extended next iteration) if forward_interval . size != 0 && forward_interval . size as isize != last_size { last_size = forward_interval . size as isize ; curr . push ( ( forward_interval , match_len + 1 ) ) ; } } if curr . is_empty ( ) { break ; } swap ( curr , prev ) ; } matches }
Find supermaximal exact matches (of length >= l) of given pattern that overlap position i in the pattern.
Find supermaximal exact matches ( of length > = l ) of given pattern that overlap position i in the pattern .
&self
pattern
&[u8]
i
usize
l
usize
example
```
use bio::alphabets::dna;
use bio::data_structures::bwt::{bwt, less, Occ};
use bio::data_structures::fmindex::{FMDIndex, FMIndex};
use bio::data_structures::suffix_array::suffix_array.

let text = b"ATTC$GAAT$";
let alphabet = dna::n_alphabet();
let sa = suffix_array(text);
let bwt = bwt(text, &sa);
let less = less(&bwt, &alphabet);
let occ = Occ::new(&bwt, 3, &alphabet);
let fm = FMIndex::new(&bwt, &less, &occ);
let fmdindex = FMDIndex::from(fm).

let pattern = b"ATT";
let intervals = fmdindex.smems(pattern, 2, 0).

let forward_positions = intervals[0].0.forward().occ(&sa);
let revcomp_positions = intervals[0].0.revcomp().occ(&sa);
let pattern_position = intervals[0].1;
let smem_len = intervals[0].2.

assert_eq!(forward_positions, [0]);
assert_eq!(revcomp_positions, [6]);
assert_eq!(pattern_position, 0);
assert_eq!(smem_len, 3);
```
` ` ` use bio :: alphabets :: dna ; use bio :: data_structures :: bwt :: { bwt less Occ } ; use bio :: data_structures :: fmindex :: { FMDIndex FMIndex } ; use bio :: data_structures :: suffix_array :: suffix_array . let text = b " ATTC$GAAT$ " ; let alphabet = dna :: n_alphabet () ; let sa = suffix_array ( text ) ; let bwt = bwt ( text &sa ) ; let less = less ( &bwt &alphabet ) ; let occ = Occ :: new ( &bwt 3 &alphabet ) ; let fm = FMIndex :: new ( &bwt &less &occ ) ; let fmdindex = FMDIndex :: from ( fm ) . let pattern = b " ATT " ; let intervals = fmdindex . smems ( pattern 2 0 ) . let forward_positions = intervals [ 0 ] . 0 . forward () . occ ( &sa ) ; let revcomp_positions = intervals [ 0 ] . 0 . revcomp () . occ ( &sa ) ; let pattern_position = intervals [ 0 ] . 1 ; let smem_len = intervals [ 0 ] . 2 . assert_eq! ( forward_positions [ 0 ] ) ; assert_eq! ( revcomp_positions [ 6 ] ) ; assert_eq! ( pattern_position 0 ) ; assert_eq! ( smem_len 3 ) ; ` ` `