{"id":778,"date":"2017-03-24T13:44:51","date_gmt":"2017-03-24T21:44:51","guid":{"rendered":"http:\/\/www.tech.dimprash.com\/?p=778"},"modified":"2017-03-24T13:49:07","modified_gmt":"2017-03-24T21:49:07","slug":"longest-substring-between-2-strings","status":"publish","type":"post","link":"http:\/\/www.tech.dimprash.com\/?p=778","title":{"rendered":"Longest Substring between 2 Strings"},"content":{"rendered":"

Algorithm:
\n1) Make a matrix m x n where m = string1 length and n = string2 length
\n2) if str1[i] != str2[j] then put matrix element as 0
\n3) if str1[i] == str2[j] then put matrix element as 1 + previous diagonal element. set max
\n4) form the longest substring by examining max element in matrix and going back diagonally to collect previous characters <\/p>\n

\r\n$str1 = \"GeeksForGeeks\";\r\n$str2 = \"AllGeeksQuiz\";\r\n$len1 = strlen($str1);\r\n$len2 = strlen($str2);\r\n$matrix = array();\r\n$max = 0;\r\nfor ($i = 0; $i < $len1 ; $i++) {\r\n    for ($j = 0; $j < $len2 ; $j++) {\r\n        if ($str1[$i] == $str2[$j]) {\r\n            if (($i == 0) || ($j == 0))\r\n                $matrix[$i][$j] = 1;\r\n            else\r\n                $matrix[$i][$j] = $matrix[$i-1][$j-1] + 1;\r\n            if ($matrix[$i][$j] > $max) {\r\n                $maxI = $i;\r\n                $maxJ = $j;\r\n                $max = $matrix[$i][$j];\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\nif ($max > 0) {\r\n    $substring = '';\r\n    for ($k = 0; $k < $max ; $k++) {\r\n        $substring = $str1[$maxI-$k] . $substring;\r\n    }\r\n    echo \"Longest Substring: $substring\\n\";\r\n} else {\r\n    echo \"No substring\\n\";\r\n}\r\n\r\n<\/pre>\n
https:\/\/www.youtube.com\/watch?v=BysNXJHzCEs<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Algorithm: 1) Make a matrix m x n where m = string1 length and n = string2 length 2) if str1[i] != str2[j] then put matrix element as 0 3) if str1[i] == str2[j] then put matrix element as 1 + previous diagonal element. set max 4) form the longest substring by examining max element … Continue reading Longest Substring between 2 Strings<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-778","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\/778","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=778"}],"version-history":[{"count":3,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/778\/revisions"}],"predecessor-version":[{"id":781,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/778\/revisions\/781"}],"wp:attachment":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=778"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=778"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=778"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}