|
<?php
class KMP {
public $da;
private $an;
public $pa;
private $pn;
public function find() {
$this->an = count($this->da);
$this->pn = count($this->pa);
$next = $this->make_next();
$i = $j = $n = 0;
// 要怪也怪我们眼力不好，两个函数相似度这么高！
while ($i < $this->an) {
$n++;
if ($this->da[$i] == $this->pa[$j] || $j == -1) {
$i++;
$j++;
} else {
$j = $next[$j];
}
if ($j == $this->pn) {
$rst = $i - $this->pn;
break;
}
}
return $rst;
}
private function make_next() {
$next = array(-1);
$j = 0;
$k = -1;
while ($j < $this->pn - 1) {
if ($k == -1 || $this->pa[$j] == $this->pa[$k]) {
$j++;
$k++;
$next[$j] = $k;
} else {
$k = $next[$k]; // 其实从这里已经能看出填空的答案了。。。
}
}
return $next;
}
public function show() {
$n = $this->find();
echo '<b>Result:</b> ', $n, '<br>';
}
}
?>
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>Untitled Document</title>
</head>
<body>
<?php
$kmp = new KMP();
$kmp->da = array(1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 2, 3);
$kmp->pa = array(1, 2, 1, 1, 2, 1, 1, 1, 2);
$kmp->show();
?>
</body>
</html>
|
