Created
September 6, 2019 08:41
-
-
Save yasaryousuf/78cde04df44b696ca46925cc9f036b97 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
// A O(n^2) time and O(1) space program to find the longest palindromic substring | |
// A utility function to print a substring str[low..high] | |
function printSubStr($str, $low, $high) | |
{ | |
for( $i = $low; $i <= $high; ++$i ) | |
echo $str[$i]; | |
} | |
// This function prints the longest palindrome substring (LPS) | |
// of str[]. It also returns the length of the longest palindrome | |
function longestPalSubstr($str) | |
{ | |
$maxLength = 1; // The result (length of LPS) | |
$start = 0; | |
$len = strlen($str); | |
// One by one consider every character as center point of | |
// even and length palindromes | |
for ($i = 1; $i < $len; ++$i) | |
{ | |
// Find the longest even length palindrome with center points | |
// as i-1 and i. | |
$low = $i - 1; | |
$high = $i; | |
while ($low >= 0 && $high < $len && $str[$low] == $str[$high]) | |
{ | |
if ($high - $low + 1 > $maxLength) | |
{ | |
$start = $low; | |
$maxLength = $high - $low + 1; | |
} | |
--$low; | |
++$high; | |
} | |
// Find the longest odd length palindrome with center | |
// point as i | |
$low = $i - 1; | |
$high = $i + 1; | |
while ($low >= 0 && $high < $len && $str[$low] == $str[$high]) | |
{ | |
if ($high - $low + 1 > $maxLength) | |
{ | |
$start = $low; | |
$maxLength = $high - $low + 1; | |
} | |
--$low; | |
++$high; | |
} | |
} | |
echo "Longest palindrome substring is: "; | |
printSubStr($str, $start, $start + $maxLength - 1); | |
return $maxLength; | |
} | |
// Driver program to test above functions | |
$str = "forgeeksskeegfor"; | |
echo "\nLength is: ". longestPalSubstr( $str ) ; | |
return 0; | |
?> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment