An implementation of the 'longest common subsequence' algorithm for PHP.

2.0.0 2014-02-17 06:24 UTC

This package is auto-updated.

Last update: 2020-09-06 06:23:07 UTC


An implementation of the 'longest common subsequence' algorithm for PHP.

The most recent stable version is 2.0.0 Current build status image Current coverage status image

Installation and documentation

What is PHP-LCS?

PHP-LCS is a PHP implementation of an algorithm to solve the 'longest common subsequence' problem.

From Wikipedia - longest common subsequence problem:

The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). Note that subsequence is different from a substring, see substring vs. subsequence. It is a classic computer science problem, the basis of file comparison programs such as diff, and has applications in bioinformatics.


use Eloquent\Lcs\LcsSolver;

$solver = new LcsSolver;

$sequenceA = array('B', 'A', 'N', 'A', 'N', 'A');
$sequenceB = array('A', 'T', 'A', 'N', 'A');

// calculates the LCS to be array('A', 'A', 'N', 'A')
$lcs = $solver->longestCommonSubsequence($sequenceA, $sequenceB);

Elements in sequences can be anything. By default, sequence members are compared using the === operator. To customize this comparison, simply construct the solver with a custom comparator, like so:

use Eloquent\Lcs\LcsSolver;

$solver = new LcsSolver(
    function ($left, $right) {
        // return true if $left and $right are equal