Оптимизировать алгоритм сравнения аналогов подстрок

Question

Я пытаюсь решить один вызов, где вам нужно проверить все строковые подстроки, являются ли они анаграммами. Условие в основном для S = abba, анаграммические пары: {S [1,1], S [4,4]}, {S [1,2], S [3,4]}, {S [2, 2], S [3,3]} и {S [1,3], S [2,4]}

Проблема в том, что у меня есть строка со 100 символами, а время выполнения должно быть ниже 9 секунд. Мое время около 50 секунд ... Ниже мой код, я буду признателен за любые советы - если вы дадите мне только указания или псевдокоды, это еще лучше.

$time1 = microtime(true); 
$string = 'abdcasdabvdvafsgfdsvafdsafewsrgsdcasfsdfgxccafdsgccafsdgsdcascdsfsdfsdgfadasdgsdfawdascsdsasdasgsdfs'; 
$arr = []; 
$len = strlen($string); 
for ($i = 0; $i < strlen($string); $i++) { 
    if ($i === 0) { 
     for ($j = 1; $j <= $len - 1; $j++) { 
      $push = substr($string, $i, $j); 
      array_push($arr, $push); 
     } 
    } else { 
     for ($j = 1; $j <= $len - $i; $j++) { 
      $push = substr($string, $i, $j); 
      array_push($arr, $push); 
     } 
    } 
} 
$br = 0; 
$arrLength = count($arr); 
foreach ($arr as $key => $val) { 
    if ($key === count($arr) - 1) { 
     break; 
    } 
    for ($k = $key + 1; $k < $arrLength; $k++) { 
     if (is_anagram($val, $arr[$k]) === true) { 
      $br++; 
     } 
    } 
} 
    echo $br."</br>"; 


function is_anagram($a, $b) 
{ 
    $result = (count_chars($a, 1) == count_chars($b, 1)); 
    return $result; 
} 
$time2 = microtime(true); 
echo "Script execution time: ".($time2-$time1); 

Edit:

Привет еще раз, сегодня у меня было некоторое время, так что я пытался оптимизировать, но не смог взломать этот ... Это мой новый код, но я думаю, что это еще хуже. Любые расширенные предложения?

<?php 

$string = 'abdcasdabvdvafsgfdsvafdsafewsrgsdcasfsdfgxccafdsgccafsdgsdcascdsfsdfsdgfadasdgsdfawdascsdsasdasgsdfs';  
$arr = []; 
$len = strlen($string); 
for ($i = 0; $i < strlen($string); $i++) { 
    if ($i === 0) { 
     for ($j = 1; $j <= $len - 1; $j++) { 

      $push = substr($string, $i, $j); 
      array_push($arr, $push); 
     } 
    } else { 
     for ($j = 1; $j <= $len - $i; $j++) { 
      $push = substr($string, $i, $j); 
      array_push($arr, $push); 
     } 
    } 
} 

$br = 0; 
$arrlen = count ($arr); 
foreach ($arr as $key => $val) { 
    if (($key === $arrlen - 1)) { 
     break; 
    } 

    for ($k = $key + 1; $k < $arrlen; $k++) { 

    $result = stringsCompare($val,$arr[$k]); 
     if ($result === true) 
     { 
      $br++; 
     } 

} 

    echo $br."\n"; 
} 

function stringsCompare($a,$b) 
{ 
    $lenOne = strlen($a); 
    $lenTwo = strlen ($b); 
    if ($lenOne !== $lenTwo) 
    { 
     return false; 
    } 
    else { 
     $fail = 0; 
     if ($lenOne === 1) { 
      if ($a === $b) { 
       return true; 
      } 
      else 
      { 
       return false; 
      } 
     } 
     else 
     { 
     for ($x = 0; $x < $lenOne; $x++) 
     { 
     $position = strpos($b,$a[$x]); 
      if($position === false) 
      { 
       $fail = 1; 
       break; 

      } 
      else 
      { 
       $b[$position] = 0; 
       $fail = 0; 
      } 
     } 
     if ($fail === 1) 
     { 
      return false; 
     } 
      else 
      { 
       return true; 
      } 
    } 
     } 
} 
?> 

Answer 1

Вы должны думать о другом правиле, которое может встретить все анаграммы определенной строки. Например, что-то о количестве вхождений каждого символа.