KMP Count Pattern

KMP Count Pattern

Hard PHP PHP Strings 31 views
Explanation Complexity

Problem Statement

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.

Example

abababa
aba
3

Constraints

Total chars

Input / Output Format

Input Format
Two lines: s then p.
Output Format
One integer count.
Constraints
Total chars

Examples

Input:
abababa aba
Output:
3

Example Solution (Public)

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

Official Solution Code

<?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;
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.