File manager - Edit - /var/www/payraty/helpdesk/vendor/webd/language/src/webd/language/LCS.php
Back
<?php namespace webd\language; /** * The longest common subsequence (LCS) problem consists in finding the * longest subsequence common to two (or more) sequences. It differs from * problems of finding common substrings: unlike substrings, subsequences are * not required to occupy consecutive positions within the original sequences. * * Used by the diff utility, by Git for reconciling multiple changes, etc. */ class LCS { private $C = array(); private $X = ""; private $Y = ""; public function __construct($str1, $str2) { $this->X = $str1; $this->Y = $str2; $m = strlen($str1); $n = strlen($str2); $this->C = array(); for ($i = 0; $i <= $m; $i++) { $this->C[$i][0] = 0; } for ($j = 0; $j <= $n; $j++) { $this->C[0][$j] = 0; } for ($i = 1; $i <= $m; $i++) { for ($j = 1; $j <= $n; $j++) { if ($str1[$i-1] == $str2[$j-1]) { $this->C[$i][$j] = $this->C[$i-1][$j-1] + 1; } else { $this->C[$i][$j] = max($this->C[$i][$j-1], $this->C[$i-1][$j]); } } } //for i := 1..m // for j := 1..n // if X[i] = Y[j] // C[i,j] := C[i-1,j-1] + 1 // else // C[i,j] := max(C[i,j-1], C[i-1,j]) } public function length() { return $this->C[strlen($this->X)][strlen($this->Y)]; } public function __toString() { return $this->value(); } public function value() { return $this->backtrack(strlen($this->X), strlen($this->Y)); } /** * Edit distance when only insertion and deletion is allowed (no * substitution) * = strlen(str1) + strlen(str2) - 2 * length(LCS(str1, str2)) * @param type $string1 * @param type $string2 */ public function distance() { return strlen($this->X) + strlen($this->Y) - 2 * $this->length(); } private function backtrack($i, $j) { if ($i == 0 || $j == 0) { return ""; } if ($this->X[$i-1] == $this->Y[$j-1]) { return $this->backtrack($i-1, $j-1) . $this->X[$i-1]; } if ($this->C[$i][$j-1] > $this->C[$i-1][$j]) { return $this->backtrack($i, $j-1); } return $this->backtrack($i-1, $j); // function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j) // if i = 0 or j = 0 // return "" // else if X[i] = Y[j] // return backtrack(C, X, Y, i-1, j-1) + X[i] // else // if C[i,j-1] > C[i-1,j] // return backtrack(C, X, Y, i, j-1) // else // return backtrack(C, X, Y, i-1, j) } // /** // * Edit distance when only insertion and deletion is allowed (no // * substitution) // * = strlen(str1) + strlen(str2) - 2 * length(LCS(str1, str2)) // * @param type $string1 // * @param type $string2 // */ // public static function distance($str1, $str2) { // return strlen($str1) + strlen($str2) - 2 * self::length($str1, $str2); // } // // public static function lcs($str1, $str2) { // $lcs = new LCS($str1, $str2); // return $lcs->backtrack(strlen($str1), strlen($str2)); // } // /** // * // * @param type $string1 // * @param type $string2 // */ // public static function length($string1, $string2) { // $lcs = new LCS($str1, $str2); // return $lcs->C; // // } }
| ver. 1.4 |
Github
|
.
| PHP 8.3.30 | Generation time: 0 |
proxy
|
phpinfo
|
Settings