trie的运用
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了trie的运用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2474字，纯文字阅读大概需要4分钟。
内容图文
trie 的应用应 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");
}
function __call($method, $param) {
if($this->debug) printf("偏移:%d 回溯:%d\n", $this->input, $this->backtracking);
}
}
------最佳解决方案--------------------
字典树，先读入文本（多个字符串），然后查找一个串在文本中出现过几次等相关应用。。。
复杂度就等于这个串的长度。。。。。
优点： 速度快
缺点： 空间花销大
------其他解决方案--------------------
多谢了，现在有点明白了，做个模型，实战理解去了。
内容总结
以上是互联网集市为您收集整理的trie的运用全部内容，希望文章能够帮你解决trie的运用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】