Hoa central
Search.php
Go to the documentation of this file.
1 <?php
2 
37 namespace Hoa\Ustring;
38 
47 class Search
48 {
58  public static function approximated($y, $x, $k)
59  {
60  $x = (string) $x;
61  $y = (string) $y;
62  $m = strlen($x);
63  $n = strlen($y);
64  $offset = [];
65  $L = [-1 => array_fill(-1, $n - $m + $k + 3, -2)];
66 
67  for ($q = 0, $max = $k - 1; $q <= $max; ++$q) {
68  $L[$q][-$q - 1] = $L[$q][-$q - 2] = $q - 1;
69  }
70 
71  for ($q = 0; $q <= $k; ++$q) {
72  for ($d = -$q, $max = $n - $m + $k - $q; $d <= $max; ++$d) {
73  $l = min(
74  max(
75  $L[$q - 1][$d - 1],
76  $L[$q - 1][$d ] + 1,
77  $L[$q - 1][$d + 1] + 1
78  ),
79  $m - 1
80  );
81  $a = substr($x, $l + 1, $m - $l);
82  $b = substr($y, $l + 1 + $d, $n - $l - $d);
83  $L[$q][$d] = $l + static::lcp($a, $b);
84 
85  if ($L[$q][$d] == $m - 1 ||
86  $d + $L[$q][$d] == $n - 1) {
87  $j = $m + $d;
88  $i = max(0, $j - $m);
89  $offset[$q][] = ['i' => $i, 'j' => $j, 'l' => $j - $i];
90  }
91  }
92  }
93 
94  return empty($offset) ? $offset : $offset[$k];
95  }
96 
104  public static function lcp($x, $y)
105  {
106  $max = min(strlen($x), strlen($y));
107  $i = 0;
108 
109  while ($i < $max && $x[$i] == $y[$i]) {
110  ++$i;
111  }
112 
113  return $i;
114  }
115 }
static approximated($y, $x, $k)
Definition: Search.php:58
static lcp($x, $y)
Definition: Search.php:104