File Coverage

blib/lib/String/LCSS.pm

Criterion	Covered	Total	%
statement	49	49	100.0
branch	19	20	95.0
condition			n/a
subroutine	6	6	100.0
pod	0	1	0.0
total	74	76	97.3

package String::LCSS;
use base ( 'Exporter' );

use utf8;
BEGIN
{
use strict;
use vars qw( $VERSION @EXPORT_OK);

	$VERSION = "0.12";

	@EXPORT_OK = qw( lcss );
}


sub lcss
{
my ($a, $b) = @_;
my (@x, @y);
my ($maxLength, $maxXi, $maxXk, $switch) = (0,0,0,0);
my $returnString;


	my $m = length ( $a );
	my $n = length ( $b );

	if ( $m > $n ) {
		( $m, $n ) = ( $n, $m );
		( $a, $b ) = ( $b, $a );
		$switch = 1;
	}

	@x = split ( //, $a );
	@y = split ( //, $b );

	#
	# declare varialbes outside of loops for a hair more speed.
	#
	my ( $i, $ii, $j, $k, $length, $xi, $xj );

	for ( $k = 0; $k < $n; $k++ ) {
		#
		# abort if the remainder of the string to check is
		# less than the common substring length already found
		#
		last if ( $maxLength >= ( $m - $k ) );

		( $xi, $length ) = ( 0, 0 );

		for ( $i = 0; $i < $m; $i++ ) {
			$j = $k;
			$length = 0;
			for ( $ii = 0; $ii < ($m-$i); $ii++ ) {
				if ( $x[$i+$ii] eq $y[$j] ) {
					$xi = $i+$ii unless ( $length );
					$xj = $j unless ( $length );
					$length++;
					$j++;
				}
				elsif ( $length ) {
					if ( $length > $maxLength ) {
						$maxLength = $length;
						$maxXi = $xi;
						$maxXk = $xj;
					}
					last;
				}
			}
		}
	}

	if ( $maxLength > 1 ) {
		for ($i = $maxXi; $i < $maxXi+$maxLength; $i++ ) {
			$returnString .= $x[$i];
		}
		($maxXi, $maxXk) = ($maxXk, $maxXi) if ( $switch );
	}

	( wantarray ) ? ( $returnString, $maxXi, $maxXk ) :  $returnString;
}



#########################################################
# Do not change this, Do not put anything below this.
# File must return "true" value at termination
1;
##########################################################

__END__