信号匹配——KMP算法填空_藍橋杯吧

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


內容：
用戶名：	您目前是匿名發表。
驗證碼：
	看不清？換一張

信号匹配——KMP算法填空

回覆帖子