{"id":175,"date":"2014-05-22T05:14:29","date_gmt":"2014-05-22T13:14:29","guid":{"rendered":"http:\/\/www.tech.dimprash.com\/?p=175"},"modified":"2017-03-26T12:41:09","modified_gmt":"2017-03-26T20:41:09","slug":"algorithms","status":"publish","type":"post","link":"http:\/\/www.tech.dimprash.com\/?p=175","title":{"rendered":"Find Longest Palindrome in a string"},"content":{"rendered":"<p><strong>Find longest palindrome in a string. <\/strong><\/p>\n<p>Brute Force: N^3<\/p>\n<p>Below Method by Dynamic Programming is N^2. Video for below method:<br \/>\n <a href=\"https:\/\/www.youtube.com\/watch?v=obBdxeCx_Qs\">https:\/\/www.youtube.com\/watch?v=obBdxeCx_Qs<\/a><\/p>\n<p>There is another algorithm called Mancher&#8217;s Algorithm which is in linear time. <\/p>\n<p><strong>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. <\/strong><\/p>\n<pre>\r\n$str = \"BANANA\";\r\n$len = strlen($str);\r\n$matrix = array();\r\n$palindromeBegins = 0;\r\n$max = 1;\r\n\r\n\/\/ single letter palindromes\r\nfor ($i=0; $i < $len; $i++) {\r\n    $matrix[$i][$i] = 1;\r\n};\r\n\r\n\/\/ 2 character palindromes\r\nfor ($i=0; $i < $len-1; $i++) {\r\n    if ($str[$i] == $str[$i+1]) {\r\n        $matrix[$i][$i+1] = 1;\r\n        $max = 2;\r\n        $palindromeBegins = $i;\r\n    }\r\n}\r\n\r\n\/\/ 3 character and above\r\nfor ($curr_len=3; $curr_len <= $len ; $curr_len++) {\r\n\r\n    for ($i=0; $i < $len-$curr_len+1; $i++) {\r\n        $j = $i+$curr_len-1;\r\n        \/\/ 1. first and last chars should match\r\n        \/\/ 2. rest of string from previous calculations should be a palindrome\r\n        if (($str[$i] == $str[$j]) &#038;&#038;\r\n            ($matrix[$i+1][$j-1] == 1)) {\r\n            $matrix[$i][$j] = 1;\r\n            $max = $curr_len;\r\n            $palindromeBegins = $i;\r\n        }\r\n    }\r\n}\r\n\r\necho \"Max Palindome: $max\\n\";\r\necho \"Palindrome: \" . substr($str, $palindromeBegins, $max);\r\necho \"\\n\";\r\n<\/pre>\n<p>Another approach:<br \/>\n<a href=\"http:\/\/krenzel.org\/articles\/longest-palnidrome\">http:\/\/krenzel.org\/articles\/longest-palnidrome<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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&#8217;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 &hellip; <a href=\"http:\/\/www.tech.dimprash.com\/?p=175\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Find Longest Palindrome in a string<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-175","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/175","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=175"}],"version-history":[{"count":21,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/175\/revisions"}],"predecessor-version":[{"id":785,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/175\/revisions\/785"}],"wp:attachment":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=175"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=175"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=175"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}