1 : <?php
2 :
3 : require_once('D:\tlum\kody\Rozdzial7\interfaces\StringSearchable.php');
4 :
5 : class BoyerMoore implements StringSearchable
6 : {
7 : // sta³e klasy
8 : const CASE_SENSITIVE = true;
9 : const CASE_INSENSITIVE = false;
10 :
11 : // szukany podci¹g
12 : public $substring = 'null';
13 : public $originalSubstring = 'null';
14 :
15 : // bufor tekstowy, w którym ma nast¹piæ wyszukiwanie
16 : public $buffer = '';
17 : public $originalBuffer = '';
18 :
19 : // tablica przeskoków stworzona na podstawie podci¹gu
20 : public $jumpTable = array();
21 :
22 : // tablica wyników
23 : protected $results = array();
24 :
25 : public function __construct()
26 : {
27 : // specjalnie pozostawiono puste
28 12 : }
29 :
30 : public function __destruct()
31 : {
32 : // specjalnie pozostawiono puste
33 1 : }
34 :
35 : public function search($substring, $buffer, $caseSensitive = self::CASE_SENSITIVE)
36 : {
37 : // walidacja danych wejœciowych
38 11 : if (!is_string($substring) || strlen($substring) < 1) {
39 3 : throw new Exception("Poszukiwany podci¹g musi byæ ci¹giem tekstowym sk³adaj¹cym siê co najmniej jednego znaku.");
40 8 : } elseif (!is_string($buffer) || strlen($buffer) < 1) {
41 3 : throw new Exception("Przeszukiwany bufor musi byæ ci¹giem tekstowym sk³adaj¹cym siê co najmniej jednego znaku.");
42 5 : } elseif (!is_bool($caseSensitive)) {
43 1 : throw new Exception("Trzeci argument funkcji " . __FUNCTION__ . " musi byæ wartoœci¹ logiczn¹.");
44 : }
45 :
46 : // zeruje tablicê wyników
47 4 : $this->results = array();
48 :
49 4 : $this->substring = $substring;
50 4 : $this->originalSubstring = $substring;
51 4 : $this->buffer = $buffer;
52 4 : $this->originalBuffer = $buffer;
53 :
54 : // zamienia bufor i podci¹g na ma³e litery je¿eli wyszikiwanie ma nie braæ pod uwagê
55 : // wielkoœci liter
56 :
57 4 : if ($caseSensitive != self::CASE_SENSITIVE) {
58 1 : $this->substring = strtolower($this->substring);
59 1 : $this->buffer = strtolower($this->buffer);
60 1 : }
61 :
62 : // pobiera tablicê przeskoków
63 4 : $this->deriveJumpTable();
64 :
65 4 : $currentCharacter = strlen($this->substring) - 1;
66 4 : $substringLength = strlen($this->substring);
67 4 : $bufferLength = strlen($this->buffer);
68 :
69 4 : while ($currentCharacter < $bufferLength) {
70 :
71 4 : for ($i = $substringLength - 1; $i >= 0; $i--) {
72 :
73 : // dopasowano znak, kontynuuj ...
74 4 : if ($this->buffer{($currentCharacter - $substringLength + $i + 1)} == $this->substring{$i}) {
75 :
76 : // czy wszystkie znaki pasuj¹?
77 4 : if ($i == 0) {
78 4 : $this->results[] = $currentCharacter - $substringLength;
79 4 : $currentCharacter += $this->getJumpLength($this->buffer{$currentCharacter});
80 :
81 4 : } else {
82 4 : continue;
83 : }
84 :
85 : // nie pasuj¹, skocz dalej ...
86 4 : } else {
87 4 : $currentCharacter += $this->getJumpLength($this->buffer{$currentCharacter});
88 4 : break;
89 : }
90 4 : }
91 4 : }
92 :
93 : // zwraca true je¿eli dopasowano choæ jeden ci¹g lub false, je¿eli nie dopasowano
94 4 : return (sizeof($this->results) > 0);
95 : }
96 :
97 : // tworzy tabelê wyszukiwania, która okreœla, o ile znaków skoczyæ
98 : // do przodu je¿eli bie¿¹cy znak nie pasuje do wzorca
99 : protected function deriveJumpTable()
100 : {
101 4 : $maxJump = strlen($this->substring);
102 :
103 : // pêtla poprzez litery
104 4 : for ($i = strlen($this->substring) - 2; $i >= 0; $i--) {
105 4 : if (!array_key_exists($this->substring{$i}, $this->jumpTable)) {
106 4 : $this->jumpTable[$this->substring{$i}] = $maxJump - $i - 1;
107 4 : }
108 4 : }
109 4 : }
110 :
111 : // zwraca tablicê przeskoków
112 : public function getJumpTable()
113 : {
114 0 : return $this->jumpTable;
115 : }
116 :
117 : // zwraca tablicê wyników
118 : public function getResults()
119 : {
120 0 : return $this->results;
121 : }
122 :
123 : // ile wyst¹pieñ znaleziono?
124 : public function getResultsCount()
125 : {
126 4 : return sizeof($this->results);
127 : }
128 :
129 : // za pomoc¹ tablicy przeskoków okreœla o ile
130 : // przemieœciæ siê w buforze
131 : public function getJumpLength($character)
132 : {
133 4 : if (array_key_exists($character, $this->jumpTable)) {
134 4 : return $this->jumpTable[$character];
135 : } else {
136 4 : return strlen($this->substring);
137 : }
138 : }
139 : }
140 :
|