head

B<AlgorithmsIT> - Provides some functions from I<Introduction to Algorithms>, Third Edition


code

=begin code :lang<raku>

use AlgorithmsIT :ALL;
use Classes;
my $P = ArrayOneBased.new: "pattern";
my $T = ArrayOneBased.new: "some text with pattern in it (or not)";
my $pi = ArrayOneBased.new: 1, $T.length; # creates an array: [1, 2, ..., $T.length]
my @matches = KMP-Matcher $T, $P;
say @matches.gist; 
# OUTPUT: «[15]␤» # 15 shifts from the first character to the match position
# The @matches array would be empty if no match were found.
=end code


B<AlgorithmsIT> is a collection of a small subset of functions in Reference 1.


See more details at L<FUNCTIONS|./FUNCTIONS.md>


Thanks to my Raku friend, '@tonyo' (on IRC #raku), for his help with the B<ArrayOneBased> class.
See his many Raku contributions at C<https://github.com/tony-o/>.


1. Thomas H. Cormen, et alii, I<Introduction to Algorithms>, Third Edition, February 2009.


This library is free software; you may redistribute it or modify it under the Artistic License 2.0.


root

para

L<Examples| file:../examples/index.podlite>


L<Download |file:../download/index.podlite>


React

=begin React :component<HeaderCol> :id<menu> 
=para L<Documentation|/doc/introduction>
=para L<Modules| /mods>
=para L<Examples| file:../examples/index.podlite>
=para L<Download |file:../download/index.podlite>
=para L<About|file:../about/index.podlite>
=para 🔍 K<⌘K>/K<ctrl-K>
=end React


HEADER

FOOTER

README

FUNCTIONS

Functions from I<Introduction to Algorithms, Third Edition>


The functions below have been translated from the I<psuedo code>
in the book into I<Raku>. To ease the translation, Raku classes were
created to mimic contructs in the pseudo code as much as
possible.


(Note the class has a short name for convenience: C<A1B>.)


The main feature of this class is that its first slot is at index 1 as
opposed to 0 in Raku arrays. Only necessary features of a normal array
have been added, so its feature list is not exhaustive. However, users
are encouraged to ask for additional features or submit a PR for such.


The class provides the following ways to instantiate an array:


=begin code
my $a = ArrayOneBased.new;
=end code


=begin code
my $a = ArrayOneBased.new: "abbxide x";
=end code


As an array filled with a number sequence M..N


=begin code
my $a = ArrayOneBased.new: 2, 6;
=end code


Specifying end only (beginning is 1 by default):


=begin code
my $a = ArrayOneBased.new: 5;
=end code


=begin code
my $a = ArrayOneBased.new: @list;
=end code


The following two functions are used to employ the I<Knuth-Morris-Pratt> (KMP) 
algorithms for pattern matching. See examples of their use in the test routines.


The functions will find all non-overlapping matches of a specified pattern in
an input text string. (It should be very useful in DNA analysis.) Following is
an example of a pattern and its matches. The results of a KMP pattern match
is a list of the "shifts" for each match. A shift is a number representing
the number of characters after the first character of the input string.
No shifts will be reported for a situation with no matches. Of course
an attempted match of an input string with a longer pattern will
result in no match.


A pattern: "AACT". A DNA string: "AAACTTTAACTAA" (13 characters).


=begin code
    AAACTTTAACTAA  # 13 characters in this string
     AACT  AACT    # two matches: the 1st at a shift of 1, the 2nd is at a shift of 7
=end code


Following is the pseudo code from Ref. 1:


=begin code
 1  n = T.length
 2  m = P.length
 3  pi = Compute-Prefix-Function(P)
 4  q = 0                                            // number of characters matched
 5  for i = 1 to n                                   // scan the text from left to right
 6      while q > 0 and P[q + 1] not equal T[i]
 7          q = pi[q]                                // next character does not match
 8      if P[q + 1] == T[i]
 9          q = q + 1                                // next character matches
10      if q == m                                    // is all of P matched?
11          print "Pattern occurs with shift" i - m
12          q = pi[q]                                // look for the next match
=end code


Line 12 is in error and should read: C<q = 0> (a bug report has been filed
with the publisher).


=begin code
KMP-Matcher(ArrayOneBased $T, ArrayOneBased $P --> List)
{...}
=end code


B<Compute-Prefix-Function> (Ref. 1, p. 1006)


=begin code
 1  m = P.length
 2  let pi[1..m] be a new array
 3  pi[1] = 0
 4  k = 0
 5  for q = 2 to m
 6      while k > 0 and P[k + 1] not equal P[q]
 7          k = pi[k]
 8      if P[k + 1] == P[q]
 9          k = k + 1
10      pi[q] = k
11  return pi
=end code


=begin code
Compute-Prefix-Function(ArrayOneBased $P --> ArrayOneBased)
{...}
=end code


The Raku Knowledge Base


=begin React :component<HeaderCol> :id<footer>  
=begin nested :!nested
=item1 B<Language>
    =item2 L<Get started|file:../getting-started/getting-started.podlite>
    =item2 L<Why Raku?|/doc/language/faq#Why-should-I-learn-Raku-What's-so-great-about-it>
    =item2 L<Try Raku|https://glot.io/new/raku>
    =item2 L<Raku cheat sheet|https://github.com/Raku/mu/blob/master/docs/Perl6/Cheatsheet/cheatsheet.txt>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<Raku on Exercism|https://exercism.org/tracks/raku>
    =item2 L<Wikipedia|https://en.wikipedia.org/wiki/Raku_(programming_language)>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=begin nested :!nested

=item1 B<L<Documentation|/doc>>
    =item2 L<Getting started, Migration guides from other languages, & Tutorials | file:../doc/introduction.podlite>
    =item2 L<Language References|file:../doc/reference.podlite>
    =item2 L<Type Reference| file:../doc/types.podlite>
    =item2 L<Miscellaneous| file:../doc/miscellaneous.podlite>
    =item2 L<FAQs (Frequently Asked Questions)|/doc/language/faq>
    =item2 L<Community|/doc/language/community>
    =item2 L<The list of all documents|file:../doc/index.podlite>

=item1 B<Resources>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>

=end nested
=begin nested :!nested

=item1 B<Resoures>
    =item2 L<Download | file:../download/index.podlite>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=item1 B<Learning>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Wikibook |https://en.wikibooks.org/wiki/Raku_Programming>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>
    =item2 L<Learn Raku in Y minutes|https://learnxinyminutes.com/docs/raku/>
    =item2 L<Golfing |https://github.com/AlexDaniel/raku-golf-cheatsheet>
=end nested
=begin nested :!nested

=item1 B<Explore>
    =item2 L<Raku Blog Aggregator|https://planet.raku.org/>
    =item2 L<Rakudo Weekly|https://rakudoweekly.blog/>
    =item2 L<The Weekly Challenge |https://perlweeklychallenge.org/>
    =item2 L<Raku Advent Calendar|https://raku-advent.blog/>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=end React


=begin React :component<CookieConsent> :id<CookieConsent> :buttonCaption("Got it!")
=para
This website uses cookies for analytics.
=end React


README

NAME

SYNOPSIS

DESCRIPTION

Credits

References

1. Thomas H. Cormen, et alii, Introduction to Algorithms, Third Edition, February 2009.

AUTHOR

COPYRIGHT AND LICENSE

AlgorithmsIT v0.0.1

Authors

License

Dependencies

Test Dependencies

Provides

Documentation