用 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 。