KMP Count Pattern
PHP
Hard
6 views
Problem Description
Count how many times pattern p appears in s (overlaps allowed) using KMP.
Input Format
Two lines: s then p.
Output Format
One integer count.
Official Solution
<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$s=$inputLines[0] ?? '';
$p=$inputLines[1] ?? '';
$m=strlen($p);
if($m===0){ echo 0; exit; }
$pi=array_fill(0,$m,0);
for($i=1,$j=0;$i<$m;$i++){
while($j>0 && $p[$i]!==$p[$j]) $j=$pi[$j-1];
if($p[$i]===$p[$j]) $j++;
$pi[$i]=$j;
}
$cnt=0;
for($i=0,$j=0,$n=strlen($s);$i<$n;$i++){
while($j>0 && $s[$i]!==$p[$j]) $j=$pi[$j-1];
if($s[$i]===$p[$j]) $j++;
if($j===$m){
$cnt++;
$j=$pi[$j-1];
}
}
echo $cnt;
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!