神仙的仙居

用 php 写了一个简单的 Trie 树，可以用来做字符串匹配。

<?php

$words = array(
'123','145','43'
);

class Trie {
    /**
     *
     * 节点数组。每个节点为二元组，依次为是否叶子节点，子节点.
     * @var array $nodes
     */
    protected $nodes;

    /**
     *
     * @var array $words 关键词数组
     */
    function __construct($words) {
        $this->nodes = array( array(false, array()) ); //初始化，添加根节点
        $p = 1; //下一个要插入的节点号
        foreach ($words as $word) {
            $cur = 0; //当前节点号
            for ($len = strlen($word), $i = 0; $i < $len; $i++) {
                $c = ord($word[$i]);
                if (isset($this->nodes[$cur][1][$c])) { //已存在就下移
                    $cur = $this->nodes[$cur][1][$c];
                    continue;
                }
                $this->nodes[$p]= array(false, array()); //创建新节点
                $this->nodes[$cur][1][$c] = $p; //在父节点记录子节点号
                $cur = $p; //把当前节点设为新插入的
                $p++; //
            }
            $this->nodes[$cur][0] = true; //一个词结束，标记叶子节点
        }
    }

    function match($s) {
        $ret = array();
        $cur = 0; //当前节点，初始为根节点
        $i = 0; //字符串当前偏移
        $p = 0; //字符串回溯位置
        $len = strlen($s);
        while($i < $len) {
            $c = ord($s[$i]);
            if (isset($this->nodes[$cur][1][$c])) { //如果存在
                $cur = $this->nodes[$cur][1][$c]; //下移当前节点
                if ($this->nodes[$cur][0]) { //是叶子节点，单词匹配！
                    $ret[$p] = substr($s, $p, $i - $p + 1); //取出匹配位置和匹配的词
                    $p = $i + 1; //设置下一个回溯位置
                    $cur = 0; //重置当前节点为根节点
                }
            } else { //不匹配
                $cur = 0; //重置当前节点为根节点
                $i = $p; //把当前偏移设为回溯位置
                $p = $i + 1; //设置下一个回溯位置
            }
            $i++; //下一个字符
        }
        return $ret;
    }
}

$trie = new Trie($words);
$s = '123456787654321';
$found = $trie->match($s, $trie);
print_r($found);

结果：

Array
(
    [0] => 123
    [11] => 43
)

不知道有没有 bug 。