Find All Anagram Starts
PHP
Hard
3 views
Problem Description
Given s and p (lowercase), print all start indices where an anagram of p begins.
Input Format
Two lines: s then p.
Output Format
One line indices (space-separated).
Official Solution
<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$s=$inputLines[0] ?? '';
$p=$inputLines[1] ?? '';
$n=strlen($s); $m=strlen($p);
if($m===0 || $m>$n){ echo ''; exit; }
$need=array_fill(0,26,0);
$win=array_fill(0,26,0);
for($i=0;$i<$m;$i++) $need[ord($p[$i])-97]++;
for($i=0;$i<$m;$i++) $win[ord($s[$i])-97]++;
$ans=[];
function sameCount($a,$b){
for($i=0;$i<26;$i++) if($a[$i]!==$b[$i]) return false;
return true;
}
if(sameCount($need,$win)) $ans[]='0';
for($i=$m;$i<$n;$i++){
$win[ord($s[$i-$m])-97]--;
$win[ord($s[$i])-97]++;
if(sameCount($need,$win)) $ans[] = strval($i-$m+1);
}
echo implode(' ',$ans);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!