Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
62 / 62
100.00% covered (success)
100.00%
4 / 4
 CRAP
100.00% covered (success)
100.00%
1 / 1
StringSearch
100.00% covered (success)
100.00%
62 / 62
100.00% covered (success)
100.00%
4 / 4
 21
100.00% covered (success)
100.00%
1 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 knuthMorrisPrattSearch
100.00% covered (success)
100.00%
16 / 16
100.00% covered (success)
100.00%
1 / 1
 5
 knuthMorrisPrattShift
100.00% covered (success)
100.00%
17 / 17
100.00% covered (success)
100.00%
1 / 1
 5
 boyerMooreHorspoolSimpleSearch
100.00% covered (success)
100.00%
12 / 12
100.00% covered (success)
100.00%
1 / 1
 4
 boyerMooreHorspoolSearch
100.00% covered (success)
100.00%
17 / 17
100.00% covered (success)
100.00%
1 / 1
 6
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\System\Search
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\System\Search;
16
17/**
18 * Basic string search algorithms.
19 *
20 * @package phpOMS\System\Search
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25abstract class StringSearch
26{
27    /**
28     * @codeCoverageIgnore
29     */
30    private function __construct()
31    {
32    }
33
34    /**
35     * Find pattern in string
36     *
37     * @param string $pattern Pattern
38     * @param string $text    Text to search in
39     *
40     * @return int Match position
41     *
42     * @since 1.0.0
43     */
44    public static function knuthMorrisPrattSearch(string $pattern, string $text) : int
45    {
46        $patternSize = \strlen($pattern);
47        $textSize    = \strlen($text);
48
49        $shift = self::knuthMorrisPrattShift($pattern);
50
51        $i = 1;
52        $j = 0;
53        while ($i + $patternSize <= $textSize) {
54            while ($text[$i + $j] === $pattern[$j]) {
55                ++$j;
56                if ($j >= $patternSize) {
57                    return $i;
58                }
59            }
60
61            if ($j > 0) {
62                $i += $shift[$j - 1];
63                $j  = \max($j - $shift[$j - 1], 0);
64            } else {
65                ++$i;
66                $j = 0;
67            }
68        }
69
70        return -1;
71    }
72
73    /**
74     * Create shift array
75     *
76     * @param string $pattern Pattern
77     *
78     * @return int[]
79     *
80     * @since 1.0.0
81     */
82    private static function knuthMorrisPrattShift(string $pattern) : array
83    {
84        $patternSize = \strlen($pattern);
85        $shift       = [];
86        $shift[]     = 1;
87
88        $i = 1;
89        $j = 0;
90        while ($i + $j < $patternSize) {
91            if ($pattern[$i + $j] === $pattern[$j]) {
92                $shift[$i + $j] = $i;
93                ++$j;
94            } else {
95                if ($j === 0) {
96                    $shift[$i] = $i + 1;
97                }
98
99                if ($j > 0) {
100                    $i += $shift[$j - 1];
101                    $j  = \max($j - $shift[$j - 1], 0);
102                } else {
103                    ++$i;
104                    $j = 0;
105                }
106            }
107        }
108
109        return $shift;
110    }
111
112    /**
113     * Find pattern in string
114     *
115     * @param string $pattern Pattern
116     * @param string $text    Text to search in
117     *
118     * @return int Match position
119     *
120     * @since 1.0.0
121     */
122    public static function boyerMooreHorspoolSimpleSearch(string $pattern, string $text) : int
123    {
124        $patternSize = \strlen($pattern);
125        $textSize    = \strlen($text);
126
127        $i = 0;
128        $j = 0;
129        while ($i + $patternSize <= $textSize) {
130            $j = $patternSize - 1;
131
132            while ($text[$i + $j] === $pattern[$j]) {
133                --$j;
134                if ($j < 0) {
135                    return $i;
136                }
137            }
138
139            ++$i;
140        }
141
142        return -1;
143    }
144
145    /**
146     * Find pattern in string
147     *
148     * @param string $pattern Pattern
149     * @param string $text    Text to search in
150     *
151     * @return int Match position
152     *
153     * @since 1.0.0
154     */
155    public static function boyerMooreHorspoolSearch(string $pattern, string $text) : int
156    {
157        $patternSize = \strlen($pattern);
158        $textSize    = \strlen($text);
159
160        $shift = [];
161        for ($k = 0; $k < 256; ++$k) {
162            $shift[$k] = $patternSize;
163        }
164
165        for ($k = 0; $k < $patternSize - 1; ++$k) {
166            $shift[\ord($pattern[$k])] = $patternSize - 1 - $k;
167        }
168
169        $i = 0;
170        $j = 0;
171        while ($i + $patternSize <= $textSize) {
172            $j = $patternSize - 1;
173
174            while ($text[$i + $j] === $pattern[$j]) {
175                --$j;
176                if ($j < 0) {
177                    return $i;
178                }
179            }
180
181            $i += $shift[\ord($text[$i + $patternSize - 1])];
182        }
183
184        return -1;
185    }
186}