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

Я пытаюсь решить одну проблему, где вы должны проверить все строковые подстроки, они анаграммы. Условие в основном для 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);

Редактировать:

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

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

2

Решение

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

1

Другие решения

Других решений пока нет …