trie 的施用

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 		$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);

  }
}

------解决方案--------------------
这个是国庆中秋过节的福利么。。。
------解决方案--------------------


老大在各应我没发散分帖啊？哈哈 ...话说我早发到水区去了.嘿嘿
继续接分
------解决方案--------------------
初学绝对很有用
------解决方案--------------------
接分~~~~
是哪家的月饼啊
------解决方案--------------------
我看不到懂样
------解决方案--------------------

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系[e-mail]核实处理。

相关文章

相关视频

---

• 教你使用PHP数据库迁移工具“Phinx”
• 详解win10下PHP的安装配置（以php5.6为...
• php Swoole实现毫秒定时计划任务（详解）
• PHP+redis实现添加处理投票的方法_PHP
• trie 的施用

• this练习题
• this关键字详解
• java this关键字
• java this关键字
• this关键字的概述和应用