Question

How to find longest palindrome substring in PHP

Answer 1

function longestPalindromeSubstring($str) {
    $len = strlen($str);
    $longestLength = 1;
    $start = 0;
    
    for ($i = 0; $i < $len; $i++) {
        for ($j = $i; $j < $len; $j++) {
            $palindrome = 1;
            for ($k = 0; $k < (int)(($j - $i + 1) / 2); $k++) {
                if ($str[$i + $k] != $str[$j - $k]) {
                    $palindrome = 0;
                }
            }
            if ($palindrome != 0 && ($j - $i + 1) > $longestLength) {
                $start = $i;
                $longestLength = $j - $i + 1;
            }
        }
    }
    
    echo "Longest palindrome substring = ";
    for ($i = $start; $i <= $start + $longestLength - 1; $i++) {
        echo $str[$i];
    }
    echo "\n";
    
    return $longestLength;
}

$str = "qabcbaproggorpxyyxzv";

$result = longestPalindromeSubstring($str);

echo "Length palindrome substring length = " . $result;




/*
run:
  
Longest palindrome substring = proggorp
Length palindrome substring length = 8
  
*/

 

70+ SQL courses for beginners and professionals

Answer 2

function longestPalindromeSubstring(string $s): string {
    $start = 0;
    $end = 0;
    $length = strlen($s);

    for ($i = 0; $i < $length; $i++) {
        $len1 = expandFromCenter($s, $i, $i);       // Odd length
        $len2 = expandFromCenter($s, $i, $i + 1);   // Even length
        $len = max($len1, $len2);

        if ($len > ($end - $start)) {
            $start = $i - intdiv($len - 1, 2);
            $end = $i + intdiv($len, 2);
        }
    }

    return substr($s, $start, $end - $start + 1);
}

function expandFromCenter(string $s, int $left, int $right): int {
    while ($left >= 0 && $right < strlen($s) && $s[$left] === $s[$right]) {
        $left--;
        $right++;
    }
    
    return $right - $left - 1;
}

$str = "qabcbaproggorpxyyxzv";

$longestPalindrome = longestPalindromeSubstring($str);

echo "Longest palindrome substring = " . $longestPalindrome . "\n";
echo "Length palindrome substring length = " . strlen($longestPalindrome);



/*
run:

Longest palindrome substring = proggorp
Length palindrome substring length = 8

*/

 

70+ SQL courses for beginners and professionals