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 of 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

Please report any bugs or feature requests to bug-string-lcss_xs@rt.cpan.org, or through the web interface at http://rt.cpan.org.

If there are multiple lcss, 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) Tree::Suffix - A lcss solution based on Suffix Trees

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.

DISCLAIMER OF WARRANTY

BECAUSE THIS SOFTWARE IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE SOFTWARE, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE SOFTWARE "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE SOFTWARE IS WITH YOU. SHOULD THE SOFTWARE PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR CORRECTION.

IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE SOFTWARE AS PERMITTED BY THE ABOVE LICENCE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE SOFTWARE TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.