Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

Greatly appreciate your input Tye!

I accepted your corrections, and will adopt some of your style practices. I messed with the binary search sub a bit and may have stumbled upon a way to get the first index. I tried several random DNA strings, and it works. Please see below and let me know your thoughts, at your convenience.

thanks!

#!/usr/bin/perl use Modern::Perl '2011'; use autodie; my $str = 'atgagatacgattacagattacagatcatacgataccatacgatc$'; my @suff; # hold suffixes while ( 1 < length $str ) { # condition excludes '$' from @suff push @suff, $str; substr ( $str, 0, 1, '' ); } # lexically ordered suffix array my @indices = sort { $suff[$a] cmp $suff[$b] } 0 .. $#suff; for ( 0 .. $#indices ) { say $indices[$_]+1, ": ", $suff[ $indices[$_] ]; } my $pattern = 'tac'; # find smallest index where pattern matches first n characters of suff +ix my $start = bsearch( \@indices, $pattern ); # get consecutive positions where pattern matches first n chars of suf +fix my @positions; for my $index ( $start .. $#indices ) { if ( $suff[ $indices[ $index ] ] =~ /^$pattern/ ) { push @positions, $indices[ $index ] + 1; } else { last; } } # print results say "\nPattern \"$pattern\" found at (position: suffix):"; for my $pos ( sort{ $a <=> $b } @positions ) { chop( my $s = $suff[ $pos - 1] ); say "$pos: $s"; } sub bsearch { my ( $indref, $pat ) = @_; my $mid; my ( $lo, $hi ) = ( 0, $#$indref ); while ( 1 ) { $mid = int( ( $lo + $hi ) / 2 ); if ( $hi == $lo ) { return $mid } if( ( $pattern cmp $suff[ $indices[ $mid ] ] ) < 0 ) { $hi = $mid; } else { $lo = $mid + 1; } } return "pattern not found in string!"; } #output abualiga:~$ ./suffixArray.pl 21: acagatcatacgataccatacgatc$ 14: acagattacagatcatacgataccatacgatc$ 35: accatacgatc$ 30: acgataccatacgatc$ 40: acgatc$ 8: acgattacagattacagatcatacgataccatacgatc$ 4: agatacgattacagattacagatcatacgataccatacgatc$ 23: agatcatacgataccatacgatc$ 16: agattacagatcatacgataccatacgatc$ 33: ataccatacgatc$ 28: atacgataccatacgatc$ 38: atacgatc$ 6: atacgattacagattacagatcatacgataccatacgatc$ 43: atc$ 25: atcatacgataccatacgatc$ 1: atgagatacgattacagattacagatcatacgataccatacgatc$ 18: attacagatcatacgataccatacgatc$ 11: attacagattacagatcatacgataccatacgatc$ 45: c$ 22: cagatcatacgataccatacgatc$ 15: cagattacagatcatacgataccatacgatc$ 27: catacgataccatacgatc$ 37: catacgatc$ 36: ccatacgatc$ 31: cgataccatacgatc$ 41: cgatc$ 9: cgattacagattacagatcatacgataccatacgatc$ 3: gagatacgattacagattacagatcatacgataccatacgatc$ 32: gataccatacgatc$ 5: gatacgattacagattacagatcatacgataccatacgatc$ 42: gatc$ 24: gatcatacgataccatacgatc$ 17: gattacagatcatacgataccatacgatc$ 10: gattacagattacagatcatacgataccatacgatc$ 20: tacagatcatacgataccatacgatc$ 13: tacagattacagatcatacgataccatacgatc$ 34: taccatacgatc$ 29: tacgataccatacgatc$ 39: tacgatc$ 7: tacgattacagattacagatcatacgataccatacgatc$ 44: tc$ 26: tcatacgataccatacgatc$ 2: tgagatacgattacagattacagatcatacgataccatacgatc$ 19: ttacagatcatacgataccatacgatc$ 12: ttacagattacagatcatacgataccatacgatc$ Pattern "tac" found at (position: suffix): 7: tacgattacagattacagatcatacgataccatacgatc 13: tacagattacagatcatacgataccatacgatc 20: tacagatcatacgataccatacgatc 29: tacgataccatacgatc 34: taccatacgatc 39: tacgatc

In reply to Re^2: searching for a pattern using suffix arrays (close) by abualiga
in thread searching for a pattern using suffix arrays by abualiga

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (13)
    As of 2014-07-24 20:33 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My favorite superfluous repetitious redundant duplicative phrase is:









      Results (167 votes), past polls