view release on metacpan or  search on metacpan

Algorithm-NCS/lib/Algorithm/NCS.pm  view on Meta::CPAN

int c_ncs(
	unsigned short int *x, 
	unsigned short int *y, 
	unsigned long int xl, 
	unsigned long int yl
	){	
    unsigned long int i;
    unsigned long int j;
    unsigned long int k;
	
	xl+=1; yl+=1;
	
	unsigned short int **c = (unsigned short int**) malloc (xl * sizeof(unsigned short int*));
	for(i=0; i<xl; ++i) 
		c[i] = malloc (yl * sizeof(unsigned short int));
	for(i=0; i<xl; i++)
		for(j=0; j<yl; j++)
			c[i][j] = 0;

    for(i=1; i<xl; i++)
		for(j=1; j<yl; j++){
			c[i][j] = c[i-1][j] > c[i][j-1] ? 
			c[i-1][j] : c[i][j-1]; 
			for(k=1; k<i+1  &&  k<j+1  &&  x[i-k] == y[j-k] ; k++)
				if(c[i][j] < c[i-k][j-k] + (k+1)*k/2 ) 
					c[i][j] = c[i-k][j-k] + (k+1)*k/2;}
					
	unsigned short int result = c[xl-1][yl-1];
	for(i=0; i<xl; i++) free (c[i]);
	free(c);
    return result;
}
ENDC

# Preloaded methods go here.

sub ncs{
    return 0 unless defined $_[0] and defined $_[1] and  $_[0] ne "" and  $_[1] ne "" ;
    return xs_ncs ([unpack('U*', $_[0])], [unpack('U*', $_[1])] );
}

1;
__END__
# Below is stub documentation for your module. You'd better edit it!

=head1 NAME

Algorithm::NCS - Fast Perl extension for sequence alignment.

=head1 SYNOPSIS

  use Algorithm::NCS;
  Algorthm::NCS::ncs("ABC", "ADC");

=head1 DESCRIPTION

Number of Common Substrings (NCS) - A model and algorithm 
for sequence alignment.
The change detection problem is aimed at identifying common and
different strings and usually has non-unique solutions.  The identification of the
best alignment is canonically based on finding a
longest common subsequence
(LCS) and is widely used for various purposes.  However, many recent version
control systems prefer alternative heuristic algorithms which not only are faster
but also usually produce better alignment than finding an
LCS.
http://psta.psiras.ru/read/psta2015_1_189-197.pdf

http://elib.sfu-kras.ru/bitstream/handle/2311/19864/Znamenskij.pdf?sequence=1

http://dl.acm.org/citation.cfm?id=2977230

=head2 EXPORT

# None by default.
ncs

=head1 SEE ALSO

http://psta.psiras.ru/read/psta2015_1_189-197.pdf

http://elib.sfu-kras.ru/bitstream/handle/2311/19864/Znamenskij.pdf?sequence=1

http://dl.acm.org/citation.cfm?id=2977230

=head1 AUTHOR

Vladislav Dyachenko, E<lt>ddb@E<gt>

=head1 COPYRIGHT AND LICENSE

Copyright (C) 2016 by Vladislav Dyachenko

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


=cut