优化子串字谜比较算法

Question

我正在尝试解决一个挑战，您必须检查所有字符串子字符串是否是字谜。条件基本上是 For 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;
            }
    }
        }
}
?>

Answer 1

你应该想到另一个规则，即某个字符串的所有字谜都可以满足。比如每个字符出现的次数。

优化子串字谜比较算法

Optimize substrings anagram compare algorithm

php

algorithm

string-comparison

anagram