字符串匹配算法学习一

2008-11-03 — ringtail

1. 字符串匹配算法简介
参见《 字符串匹配算法研究 》 http://www.yuanma.org/data/2008/0806/article_3128.htm
摘要：随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量，本文力图阐明字符串匹配算法的发展过程，并介绍了各个算法的特点，并给予了适当的比较和分析。
2. Horspool算法
算法详细解释参考《算法设计与分析基础》第二版195页
这个算法的关键之处是对模式进行预处理，计算模式中每个字符到模式字符串尾的距离。
PHP代码实现如下：

$string = 'afeovfpop';
$pattern = 'vfp';
function shiftTable($pattern){
$length = strlen($pattern);
$table = array();
for($j=0;$j$length-2){
$table[$key] = $length;
}
}
return $table;
}
function Horspool($string, $pattern){
$table = shiftTable($pattern);
//	print_r($table);
$m = strlen($pattern);
$i = $m - 1;
$n = strlen($string);
while($i<=$n-1){
$k=0;
while(($k<=$m-1)&&($pattern[$m-1-$k]==$string[$i-$k])){
$k = $k+1;
}
if($k==$m){
return $i-$m+1;
}else{
$key = $pattern[$k];
$i=$i+$table[$key];
}
}
return 0;
}
echo Horspool($string,$pattern);
echo strpos($string,$pattern);
Posted in PHP. Tags: , . 没有评论 »