NAME

String::LCSS_XS - Find The Longest Common Substring of Two Strings.

SYNOPSIS

  use String::LCSS_XS;
  
  my $longest = lcss ( "zyzxx", "abczyzefg" );
  print $longest, "\n";

DESCRIPTION

String::LCSS_XS computes the Longest Common Substring shared by two strings. It is a C implementation of String::LCSS and uses a dynamic programming algorithm with both runtime and memory usage of O(mn).

EXPORT

 char* lcss(char* s, char* t)

PERFORMANCE

  my $s = 'i pushed the lazy dog into a creek, the quick brown fox told me to';
  my $t = 'the quick brown fox jumps over the lazy dog';

                    Rate    String::LCSS String::LCSS_XS
 String::LCSS     42.5/s              --           -100%
 String::LCSS_XS 32609/s          76628%              --
  

BUGS AND LIMITATIONS

Probably many.

If there are multiple lcss (with the same length), then this implementation returns only the first found.

String::LCSS_XS currently does not support String::LCSS feature in list context where it returns the lcss positions.

String::LCSS returns undef when the lcss has size 1. String::LCSS_XS returns this single character.

CREDITS

Daniel Yacob has written String::LCSS. I stole his API, test suite and SYNOPSIS.

SEE ALSO

String::LCSS - A pure perl implementation (but O(n^3) runtime)

Gusfield, Dan. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

AUTHOR

Markus Riester, <mriester@gmx.de>

COPYRIGHT AND LICENSE

Copyright (C) 2007 by Markus Riester

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.6 or, at your option, any later version of Perl 5 you may have available.