本帖最后由 xuzuning 于 2013-04-14 19:02:03 编辑
应 CSDN 要求，收到 CSDN 月饼的应发散分贴
前贴已发，由于僧多粥少。故此结贴，比继续发帖散分
class TTrie { protected $buffer = array(); protected $dict = array( array() ); protected $input = 0; //字符串当前偏移 protected $backtracking = 0; //字符串回溯位置 public $debug = 0; public $savematch = 1; function set($word, $action='') { if(is_array($word)) { foreach($word as $k=>$v) $this->set($k, $v); return; } $p = count($this->dict); $cur = 0; //当前节点号 foreach(str_split($word) as $c) { if (isset($this->dict[$cur][$c])) { //已存在就下移 $cur = $this->dict[$cur][$c]; continue; } $this->dict[$p]= array(); //创建新节点 $this->dict[$cur][$c] = $p; //在父节点记录子节点号 $cur = $p; //把当前节点设为新插入的 $p++; } $this->dict[$cur]['acc'] = $action; //一个词结束，标记叶子节点 } function match($s) { $ret = array(); $cur = 0; //当前节点，初始为根节点 $i =& $this->input; //字符串当前偏移 $p =& $this->backtracking; //字符串回溯位置 $s .= "\0"; //附加结束符 $len = strlen($s); $buf = ''; while($i < $len) { $c = $s{$i}; if(isset($this->dict[$cur][$c])) { //如果存在 $cur = $this->dict[$cur][$c]; //转到对应的位置 if(isset($this->dict[$cur][$s[$i+1]])) {//检查下一个字符是否也能匹配，长度优先 $i++; continue; } if(isset($this->dict[$cur]['acc'])) { //是叶子节点，单词匹配！ if($buf != '') { $this->buffer[] = $buf; $buf = ''; } if($this->savematch) $this->buffer[] = substr($s, $p, $i - $p + 1); //取出匹配位置和匹配的词 $ar = explode(',', $this->dict[$cur]['acc']); call_user_func_array( array($this, array_shift($ar)), $ar ); $p = $i + 1; //设置下一个回溯位置 $cur = 0; //重置当前节点为根节点 } } else { //不匹配 $buf .= $s{$p}; //substr($s, $p, $i - $p + 1); //保存未匹配位置和未匹配的内容 $cur = 0; //重置当前节点为根节点 $i = $p; //把当前偏移设为回溯位置 $p = $i + 1; //设置下一个回溯位置 } $i++; //下一个字符 } if(trim($buf, "\0")) $this->buffer[] = trim($buf, "\0"); return $this->buffer; } function __call($method, $param) { if($this->debug) printf("偏移:%d 回溯:%d\n", $this->input, $this->backtracking); }}登入後複製
回复讨论(解决方案)
这个是国庆中秋过节的福利么。。。
老大在各应我没发散分帖啊？哈哈 ...话说我早发到水区去了.嘿嘿
继续接分
初学绝对很有用
接分~~~~
是哪家的月饼啊
我看不到懂样
这代码干什么用的？没看懂……
看维基的解释，居然还是不懂…… http://zh.wikipedia.org/wiki/Trie
大学白读了……
没学过算法，看到树就知道爬
文……
这代码干什么用的？没看懂……
看维基的解释，居然还是不懂…… http://zh.wikipedia.org/wiki/Trie
大学白读了……
字典树，先读入文本（多个字符串），然后查找一个串在文本中出现过几次等相关应用。。。
复杂度就等于这个串的长度。。。。。
优点： 速度快
缺点： 空间花销大
感谢谢
严重支持这种分享精神,有分享才会有进步
EWN
收藏了嘿嘿
收藏！
接分，老大威武！
火钳刘明
谢谢徐哥
徐哥谢谢
很久没来了，以来就看到散分帖，果断接之
接月饼分， 学习， 收藏之
接分，mark下，慢慢看
果断回帖来接分！
初学绝对很有用
这代码干什么用的？没看懂……
看维基的解释，居然还是不懂…… http://zh.wikipedia.org/wiki/Trie
大学白读了……
我记得是离散或者编译原理的内容啊
果断接分 月饼拿来
好东西呀
算法贴……感觉c++写的要好看呢……
我的沙发贴子为什么给删除了，而且也没通知？黑暗？
收到！接分
楼主好人啊，谢谢
字典树，先读入文本（多个字符串），然后查找一个串在文本中出现过几次等相关应用。。。
复杂度就等于这个串的长度。。。。。
优点： 速度快
缺点： 空间花销大
多谢了，现在有点明白了，做个模型，实战理解去了。
怎么用啊。看不懂。楼主能举几个例子看看吗
持续接分ing
kan kan
中秋来接分了
恭喜，恭喜，来接接分啦！
weidejif zhihao huitiel
学习下
学习下ing。。。
学习ing
这是发月饼吗？
跟着大牛走
原来这里送分了
没看懂
唉
真悲催
版主 想请教一下
$TTrie = new TTrie();
$TTrie->set('abc');
$TTrie->set('abd');
var_dump($TTrie->dict);
array(5) {
[0]=>
array(1) {
["a"]=>
int(1)
}
[1]=>
array(1) {
["b"]=>
int(2)
}
[2]=>
array(2) {
["c"]=>
int(3)
["d"]=>
int(4)
}
[3]=>
array(1) {
["acc"]=>
string(0) ""
}
[4]=>
array(1) {
["acc"]=>
string(0) ""
}
}
那个acc有什么用的呢 是不是各自和c、d 同级才对的呢。
学习了，嘿嘿，挺好
