trie 的运用

trie 的应用
应 CSDN 要求，收到 CSDN 月饼的应发散分贴
前贴已发，由于僧多粥少。故此结贴，比继续发帖散分

class TTrie {<br />
  protected $buffer = 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 />

------最佳解决方案--------------------

引用:

这代码干什么用的？没看懂……
看维基的解释，居然还是不懂…… http://zh.wikipedia.org/wiki/Trie
大学白读了……

字典树，先读入文本（多个字符串），然后查找一个串在文本中出现过几次等相关应用。。。
复杂度就等于这个串的长度。。。。。
优点： 速度快
缺点： 空间花销大
------其他解决方案--------------------

引用:

字典树，先读入文本（多个字符串），然后查找一个串在文本中出现过几次等相关应用。。。
复杂度就等于这个串的长度。。。。。
优点： 速度快
缺点： 空间花销大

多谢了，现在有点明白了，做个模型，实战理解去了。