PHP - Longest Common Substring

PHP implementation of an algorithm to solve the longest common substring problem.

About

PHP-Longest-Common-Subsequence is a PHP implementation of an algorithm to solve the 'longest common substring' problem.

From Wikipedia - Longest common substring problem:

In computer science, the longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings.

Installation

Require triun/longest-common-substring package with composer using the following command:

composer require triun/longest-common-substring

Usage

Solver

use Triun\LongestCommonSubstring\Solver;

$solver = new Solver();

$stringA = '0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF';
$stringB = '56789AB56789ABCDE56789ABCDE56789AB56789A123456789A';

// calculates the LCSubstring to be '123456789A'
$result = $solver->solve($stringA, $stringB);

Matches solver

use Triun\LongestCommonSubstring\Solver;

$matchSolver = new MatchesSolver();

$stringA = '0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF';
$stringB = '56789AB56789ABCDE56789ABCDE56789AB56789A123456789A';

$matches = $matchSolver->solve($stringA, $stringB);

// calculates the LCSubstring to be '123456789A'
$result = "$matches";

But also can give you the rest of the results which has the same length:

var_dump($matches->values());

array:12 [
  0 => "123456789A"
  1 => "56789ABCDE"
  2 => "56789ABCDE"
  3 => "123456789A"
  4 => "56789ABCDE"
  5 => "56789ABCDE"
  6 => "123456789A"
  7 => "56789ABCDE"
  8 => "56789ABCDE"
  9 => "123456789A"
  10 => "56789ABCDE"
  11 => "56789ABCDE"
]

You can use unique to skip duplicated values:

var_dump($matches->unique());

array:2 [
  0 => "123456789A"
  1 => "56789ABCDE"
]

Or even more information about the matches, like the input strings indexes:

var_dump($matches->values());

array:12 [
  0 => array:3 [
    "value" => "123456789A"
    "length" => 10
    "indexes" => array:2 [
      0 => 1
      1 => 40
    ]
  ]
  1 => array:3 [
    "value" => "56789ABCDE"
    "length" => 10
    "indexes" => array:2 [
      0 => 5
      1 => 7
    ]
  ]
  2 => array:3 [
    "value" => "56789ABCDE"
    "length" => 10
    "indexes" => array:2 [
      0 => 5
      1 => 17
    ]
  ]
  ...
]

Issues

Bug reports and feature requests can be submitted on the Github Issue Tracker.

Contributing

See CONTRIBUTING.md for information.

License

This repository is open-sourced software licensed under the MIT license