<?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)));

最后更新于 2021-07-01 06:51:06 并被添加「」标签，已有 489 位童鞋阅读过。