Hoa central
Hoa\String\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\String\Search::approximated ( \$y, \$x, \$k )
static

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

Parameters
 string \$y Haystack. string \$x Needle. int \$k Number 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\String\Search::lcp ( \$x, \$y )
static

Length of the longest common prefixes.

Parameters
 string \$x Word. string \$y Word.
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  }

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