| 1: | <?php |
| 2: | |
| 3: | namespace nightmare; |
| 4: | |
| 5: | class trie |
| 6: | { |
| 7: | |
| 8: | public $tree; |
| 9: | |
| 10: | public function __construct() { |
| 11: | $this->tree = [ |
| 12: | 'value' => '', |
| 13: | 'child' => [] |
| 14: | ]; |
| 15: | } |
| 16: | |
| 17: | public function add($str, $data = '') { |
| 18: | $length = mb_strlen($str); |
| 19: | |
| 20: | if (!$length) { |
| 21: | return false; |
| 22: | } |
| 23: | |
| 24: | $tree = &$this->tree; |
| 25: | $chars = mb_str_split($str); |
| 26: | $i = 0; |
| 27: | |
| 28: | foreach ($chars as $char) { |
| 29: | $i++; |
| 30: | $is_end = $i === $length; |
| 31: | $char = mb_ord($char); |
| 32: | |
| 33: | if (!isset($tree['child'][$char])) { |
| 34: | $tree['child'][$char] = [ |
| 35: | 'value' => '', |
| 36: | 'child' => [] |
| 37: | ]; |
| 38: | } |
| 39: | |
| 40: | if ($is_end) { |
| 41: | $tree['child'][$char]['value'] = (string) $data; |
| 42: | } |
| 43: | |
| 44: | $tree = &$tree['child'][$char]; |
| 45: | } |
| 46: | } |
| 47: | |
| 48: | |
| 49: | public function search($str) { |
| 50: | $length = mb_strlen($str); |
| 51: | |
| 52: | if (!$length) { |
| 53: | return false; |
| 54: | } |
| 55: | |
| 56: | $tree = &$this->tree; |
| 57: | $chars = mb_str_split($str); |
| 58: | $i = 0; |
| 59: | |
| 60: | foreach ($chars as $char) { |
| 61: | $i++; |
| 62: | $is_end = $i === $length; |
| 63: | $char = mb_ord($char); |
| 64: | |
| 65: | if (!isset($tree['child'][$char])) { |
| 66: | return false; |
| 67: | } |
| 68: | |
| 69: | if ($is_end) { |
| 70: | return [ |
| 71: | 'value' => $tree['child'][$char]['value'] ?? '', |
| 72: | 'is_end' => count($tree['child'][$char]['child']) === 0 |
| 73: | ]; |
| 74: | } |
| 75: | |
| 76: | $tree = &$tree['child'][$char]; |
| 77: | } |
| 78: | } |
| 79: | } |
| 80: | |