/PHP-Longest-Common-Substring

An implementation of the `Longest common substring` algorithm for PHP.

Primary LanguagePHPMIT LicenseMIT

PHP - Longest Common Substring

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

Latest Version on Packagist Build Status Coverage status Total Downloads The most recent stable version is 2.0.0 Software License

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