海运的博客

PHP实现Trie结构

发布时间:December 24, 2014 // 分类:PHP // 1 Comment

  class Trie{
  public $tree = array();

  public function insert($str){
    $count = strlen($str);
    $T = &$this->tree;
    //关联数组递归各个字符,无则新建
    for($i = 0; $i < $count; $i++){
      $c = $str[$i];
      if (!isset($T[$c]))
        $T[$c] = array();  
      $T = &$T[$c];
    }
  }

  public function remove($chars){
    if($this->find($chars)){    
      $count = strlen($chars);
      $T = &$this->tree;
      for($i = 0;$i < $count;$i++){
        $c = $chars[$i];
        if(count($T[$c]) == 1){     
          unset($T[$c]);
          return true;
        }
        $T = &$T[$c];
      }
    }
  }

  public function find($chars){
    $count = strlen($chars);
    $T = &$this->tree;
    //循环遍历各个字符,如无则返回false
    for($i = 0;$i < $count;$i++){
      $c = $chars[$i];
      if(!array_key_exists($c, $T)){
        return false;
      }
      $T = &$T[$c];
    }
    //否则返回找到
    return true;
  }
}
$t = new Trie();
$t->insert('str');
var_dump($t->find('str'));

更多:
https://github.com/fran6co/phptrie
http://kaiserleib.com/archives/63
http://www.cnblogs.com/endsock/p/3584161.html

标签:none

有一条 关于" PHP实现Trie结构 "的评论

  1. 1

    第9行 $chars 应该为 $str

评论已关闭

分类
最新文章
最近回复
  • 海运: 地址格式和udpxy一样,udpxy和msd_lite能用这个就能用。
  • 1: 怎么用 编译后的程序在家里路由器内任意一台设备上运行就可以吗?比如笔记本电脑 m参数是笔记本的...
  • 孤狼: ups_status_set: seems that UPS [BK650M2-CH] is ...
  • 孤狼: 擦。。。。apcupsd会失联 nut在冲到到100的时候会ONBATT进入关机状态,我想想办...
  • 海运: 网络,找到相应的url编辑重发请求,firefox有此功能,其它未知。
  • knetxp: 用浏览器F12网络拦截或监听后编辑重发请求,修改url中的set为set_super,将POS...
  • Albert: 啊啊啊啊啊啊啊啊啊 我太激动了,终于好了英文区搜索了半天,翻遍了 pve 论坛没找到好方法,博...
  • jiangker: good, very helpful to me
  • fengfeng: N1 armbian 能有编译下内核吗。。我要开启can 不懂怎么操作
  • 1: 方法一ngtcp2要改下:./configure PKG_CONFIG_PATH=/usr/l...