trie 的应用
应 CSDN 要求，收到 CSDN 月饼的应发散分贴
前贴已发，由于僧多粥少。故此结贴，比继续发帖散分
class TTrie {<br /> protected $buffer = <p style="color:transparent">2本文来源gao!daima.com搞$代!码网</p><span>搞代gaodaima码</span>array();<br /> protected $dict = array( array() );<br /> protected $input = 0; //字符串当前偏移<br /> protected $backtracking = 0; //字符串回溯位置<br /> public $debug = 0;<br /> public $savematch = 1;<br /><br /> function set($word, $action='') {<br /> if(is_array($word)) {<br /> foreach($word as $k=>$v) $this->set($k, $v);<br /> return;<br /> }<br /> $p = count($this->dict);<br /> $cur = 0; //当前节点号<br /> foreach(str_split($word) as $c) {<br /> if (isset($this->dict[$cur][$c])) { //已存在就下移<br /> $cur = $this->dict[$cur][$c];<br /> continue;<br /> }<br /> $this->dict[$p]= array(); //创建新节点<br /> $this->dict[$cur][$c] = $p; //在父节点记录子节点号<br /> $cur = $p; //把当前节点设为新插入的<br /> $p++;<br /> }<br /> $this->dict[$cur]['acc'] = $action; //一个词结束，标记叶子节点<br /> }<br /><br /> function match($s) {<br /> $ret = array();<br /> $cur = 0; //当前节点，初始为根节点<br /> $i =& $this->input; //字符串当前偏移<br /> $p =& $this->backtracking; //字符串回溯位置<br /> $s .= "\0"; //附加结束符<br /> $len = strlen($s);<br /> $buf = '';<br /> while($i < $len) {<br /> $c = $s{$i};<br /> if(isset($this->dict[$cur][$c])) { //如果存在<br /> $cur = $this->dict[$cur][$c]; //转到对应的位置<br /> if(isset($this->dict[$cur][$s[$i+1]])) {//检查下一个字符是否也能匹配，长度优先<br /> $i++;<br /> continue;<br /> }<br /> if(isset($this->dict[$cur]['acc'])) { //是叶子节点，单词匹配！<br /> if($buf != '') {<br /> $this->buffer[] = $buf;<br /> $buf = '';<br /> }<br /> if($this->savematch) $this->buffer[] = substr($s, $p, $i - $p + 1); //取出匹配位置和匹配的词<br /><br /> $ar = explode(',', $this->dict[$cur]['acc']);<br /> call_user_func_array( array($this, array_shift($ar)), $ar );<br /><br /> $p = $i + 1; //设置下一个回溯位置<br /> $cur = 0; //重置当前节点为根节点<br /> }<br /> } else { //不匹配<br /> $buf .= $s{$p}; //substr($s, $p, $i - $p + 1); //保存未匹配位置和未匹配的内容<br /> $cur = 0; //重置当前节点为根节点<br /> $i = $p; //把当前偏移设为回溯位置<br /> $p = $i + 1; //设置下一个回溯位置<br /> }<br /> $i++; //下一个字符<br /> }<br /> if(trim($buf, "\0")) $this->buffer[] = trim($buf, "\0");<br /> }<br /><br /> function __call($method, $param) {<br /> if($this->debug) printf("偏移:%d 回溯:%d\n", $this->input, $this->backtracking);<br /><br /> }<br />}<br />
——解决方案——————–
这个是国庆中秋过节的福利么。。。
——解决方案——————–
老大在各应我没发散分帖啊？哈哈 …话说我早发到水区去了.嘿嘿
继续接分
——解决方案——————–
初学绝对很有用
——解决方案——————–
接分~~~~
是哪家的月饼啊
——解决方案——————–
我看不到懂样
——解决方案——————–
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：trie 的施用
转载请注明原文链接：trie 的施用
