Hoa central
Static Public Member Functions | List of all members
Hoa\Ustring\Search Class Reference

Static Public Member Functions

static approximated ($y, $x, $k)
 
static lcp ($x, $y)
 

Detailed Description

Class .

Some algorithms about search in strings.

Definition at line 47 of file Search.php.

Member Function Documentation

static Hoa\Ustring\Search::approximated (   $y,
  $x,
  $k 
)
static

Search by approximated patterns, with k differences based upon the principle diagonal monotony.

Parameters
string$yHaystack.
string$xNeedle.
int$kNumber of differences.
Returns
array

Definition at line 58 of file Search.php.

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  }

Here is the caller graph for this function:

static Hoa\Ustring\Search::lcp (   $x,
  $y 
)
static

Length of the longest common prefixes.

Parameters
string$xWord.
string$yWord.
Returns
int

Definition at line 104 of file Search.php.

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  }

Here is the caller graph for this function:


The documentation for this class was generated from the following file: