Find Longest Palindrome in a string

Find longest palindrome in a string.

Brute Force: N^3

Below Method by Dynamic Programming is N^2. Video for below method:
https://www.youtube.com/watch?v=obBdxeCx_Qs

There is another algorithm called Mancher’s Algorithm which is in linear time.

Note that here since we are dealing with single string we just need to populate top triangle of matrix. In longest substring since we were dealing with 2 strings we populated the whole matrix.

$str = "BANANA";
$len = strlen($str);
$matrix = array();
$palindromeBegins = 0;
$max = 1;

// single letter palindromes
for ($i=0; $i < $len; $i++) {
    $matrix[$i][$i] = 1;
};

// 2 character palindromes
for ($i=0; $i < $len-1; $i++) {
    if ($str[$i] == $str[$i+1]) {
        $matrix[$i][$i+1] = 1;
        $max = 2;
        $palindromeBegins = $i;
    }
}

// 3 character and above
for ($curr_len=3; $curr_len <= $len ; $curr_len++) {

    for ($i=0; $i < $len-$curr_len+1; $i++) {
        $j = $i+$curr_len-1;
        // 1. first and last chars should match
        // 2. rest of string from previous calculations should be a palindrome
        if (($str[$i] == $str[$j]) &&
            ($matrix[$i+1][$j-1] == 1)) {
            $matrix[$i][$j] = 1;
            $max = $curr_len;
            $palindromeBegins = $i;
        }
    }
}

echo "Max Palindome: $max\n";
echo "Palindrome: " . substr($str, $palindromeBegins, $max);
echo "\n";

Another approach:
http://krenzel.org/articles/longest-palnidrome