1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
<?php

class TrieNode
{
    public $data;
    public $children = [];
    public $isEndingChar = false;

    public function __construct($data)
    {
        $this->data = $data;
    }
}

class Tire
{
    private $root;

    public function __construct()
    {
        $this->root = new TrieNode('_'); //根节点
    }

    public function getRoot()
    {
        return $this->root;
    }

    public function insert($text)
    {
        $p = $this->root;
        for ($i = 0; $i < mb_strlen($text); $i++) {
            $index = $data = $text[$i];

            if (empty($p->children[$index])) {
                $newNode = new TrieNode($data);
                $p->children[$index] = $newNode;
            }
            $p = $p->children[$index];
        }
        $p->isEndingChar = true;
    }

    public function find($pattern)
    {
        $p = $this->root;
        for ($i = 0; $i < mb_strlen($pattern); $i++) {
            $index = $data = $pattern[$i];

            if (empty($p->children[$index])) {
                return false;
            }
            $p = $p->children[$index];
        }
        if ($p->isEndingChar == false) {
            return false;
        }
        return true;
    }
}

$trie = new Tire();
// 创建
$strings = ['b', 'abc', 'abd', 'bcd', 'abcd', 'efg', 'hii'];
foreach ($strings as $str) {
    $trie->insert($str);
}

// 搜索
if ($trie->find('bcd')) {
    print "包含这个字符串\n";
} else {
    print "不包含这个字符串\n";
}
var_dump(json_encode(json_decode(json_encode($trie->getRoot()), true)));