trie 的施用

WBOY
WBOYOriginal
2016-06-13 11:06:57781browse

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 />

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


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

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn