Repository: keon/algorithms
Pull request #657 (2020-05-25 15:06:14)

Update binary_search.py
Added Master Theorem solution to Binary Search


Patch:
diff --git a/README.md b/README.md
index 1fed65a..79c1d08 100644
--- a/README.md
+++ b/README.md
@@ -329,9 +329,10 @@ If you want to uninstall algorithms, it is as simple as:
     - [longest_common_prefix](algorithms/strings/longest_common_prefix.py)
     - [rotate](algorithms/strings/rotate.py)
     - [first_unique_char](algorithms/strings/first_unique_char.py)
-    - [repeat_substring](algorithms/strings/repeat_substring.py)     
-	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
-	- [knuth_morris_pratt](algorithms/strings/knuth_morris_pratt.py)
+    - [repeat_substring](algorithms/strings/repeat_substring.py)
+	  - [atbash_cipher](algorithms/strings/atbash_cipher.py)
+    - [longest_palindromic_substring](algorithms/strings/longest_palindromic_substring.py)
+  	- [knuth_morris_pratt](algorithms/strings/knuth_morris_pratt.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/bst)
         - [array_to_bst](algorithms/tree/bst/array_to_bst.py)
diff --git a/algorithms/arrays/flatten.py b/algorithms/arrays/flatten.py
index f19156a..52f4ec5 100644
--- a/algorithms/arrays/flatten.py
+++ b/algorithms/arrays/flatten.py
@@ -11,7 +11,7 @@ def flatten(input_arr, output_arr=None):
     if output_arr is None:
         output_arr = []
     for ele in input_arr:
-        if isinstance(ele, Iterable):
+        if not isinstance(ele, str) and isinstance(ele, Iterable):
             flatten(ele, output_arr)    #tail-recursion
         else:
             output_arr.append(ele)      #produce the result
@@ -25,7 +25,7 @@ def flatten_iter(iterable):
     returns generator which produces one dimensional output.
     """
     for element in iterable:
-        if isinstance(element, Iterable):
+        if not isinstance(element, str) and isinstance(element, Iterable):
             yield from flatten_iter(element)    
         else:
             yield element
diff --git a/algorithms/dp/fib.py b/algorithms/dp/fib.py
index 6762e90..7a6fd71 100644
--- a/algorithms/dp/fib.py
+++ b/algorithms/dp/fib.py
@@ -1,3 +1,17 @@
+'''
+In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence, 
+such that each number is the sum of the two preceding ones, starting from 0 and 1. 
+That is,
+    F0=0 , F1=1
+and
+    Fn= F(n-1) + F(n-2)
+The Fibonacci numbers are the numbers in the following integer sequence.
+    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….
+
+In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
+
+Here, given a number n, print n-th Fibonacci Number.
+'''
 def fib_recursive(n):
     """[summary]
     Computes the n-th fibonacci number recursive.
diff --git a/algorithms/search/binary_search.py b/algorithms/search/binary_search.py
index 644f98f..d8bccf0 100644
--- a/algorithms/search/binary_search.py
+++ b/algorithms/search/binary_search.py
@@ -1,9 +1,13 @@
 #
 # Binary search works for a sorted array.
 # Note: The code logic is written for an array sorted in
-#       increasing order.
-# T(n): O(log n)
-#
+#  increasing order.
+#For Binary Search, T(N) = T(N/2) + O(1) // the recurrence relation
+#Apply Masters Theorem for computing Run time complexity of recurrence relations : T(N) = aT(N/b) + f(N)
+#Here, a = 1, b = 2 => log (a base b) = 1 
+# also, here f(N) = n^c log^k(n) //k = 0 & c = log (a base b) So, T(N) = O(N^c log^(k+1)N) = O(log(N))
+
+
 def binary_search(array, query):
     lo, hi = 0, len(array) - 1
     while lo <= hi:
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
index 3e6bc19..72ea7d7 100644
--- a/algorithms/strings/__init__.py
+++ b/algorithms/strings/__init__.py
@@ -35,5 +35,5 @@ from .rotate import *
 from .first_unique_char import *
 from .repeat_substring import *
 from .atbash_cipher import *
+from .longest_palindromic_substring import *
 from .knuth_morris_pratt import *
-
diff --git a/algorithms/strings/longest_palindromic_substring.py b/algorithms/strings/longest_palindromic_substring.py
new file mode 100644
index 0000000..ad0c831
--- /dev/null
+++ b/algorithms/strings/longest_palindromic_substring.py
@@ -0,0 +1,44 @@
+'''
+Given string s, find the longest palindromic substring.
+
+Example1:
+
+* input: "dasdasdasdasdasdadsa"
+* output: "asdadsa"
+
+Example2:
+
+* input: "acdbbdaa"
+* output: "dbbd"
+
+Manacher's algorithm
+
+'''
+
+def longest_palindrome(s):
+    if len(s) < 2:
+        return s
+
+    n_str = '#' + '#'.join(s) + '#'
+    p = [0] * len(n_str)
+    mx, loc = 0, 0
+    index, maxlen = 0, 0
+    for i in range(len(n_str)):
+        if i < mx and 2 * loc - i < len(n_str):
+            p[i] = min(mx - i, p[2 * loc - i])
+        else:
+            p[i] = 1
+
+        while p[i] + i < len(n_str) and i - p[i] >= 0 and n_str[
+                i - p[i]] == n_str[i + p[i]]:
+            p[i] += 1
+
+        if i + p[i] > mx:
+            mx = i + p[i]
+            loc = i
+
+        if p[i] > maxlen:
+            index = i
+            maxlen = p[i]
+    s = n_str[index - p[index] + 1:index + p[index]]
+    return s.replace('#', '')


Test patch:
diff --git a/tests/test_strings.py b/tests/test_strings.py
index 48fafd2..b8750b1 100644
--- a/tests/test_strings.py
+++ b/tests/test_strings.py
@@ -38,6 +38,7 @@ from algorithms.strings import (
     first_unique_char,
     repeat_substring,
     atbash,
+    longest_palindrome,
     knuth_morris_pratt
 )
 
@@ -527,24 +528,44 @@ class TestAtbashCipher(unittest.TestCase):
     Arguments:
         unittest {[type]} -- [description]
     """
-    
+
     def test_atbash_cipher(self):
         self.assertEqual("zyxwvutsrqponml", atbash("abcdefghijklmno"))
         self.assertEqual("KbgslM", atbash("PythoN"))
         self.assertEqual("AttaCK at DawN", atbash("ZggzXP zg WzdM"))
         self.assertEqual("ZggzXP zg WzdM", atbash("AttaCK at DawN"))
+
+
+
+class TestLongestPalindromicSubstring(unittest.TestCase):
+    """[summary]
+    Test for the file longest_palindromic_substring.py
+    
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    
+    def test_longest_palindromic_substring(self):
+        self.assertEqual("bb", longest_palindrome("cbbd"))
+        self.assertEqual("abba", longest_palindrome("abba"))
+        self.assertEqual("asdadsa", longest_palindrome("dasdasdasdasdasdadsa"))
+        self.assertEqual("abba", longest_palindrome("cabba"))
+
         
 class TestKnuthMorrisPratt(unittest.TestCase):
     """[summary]
     Test for the file knuth_morris_pratt.py
 
+
     Arguments:
         unittest {[type]} -- [description]
     """
+
     def test_knuth_morris_pratt(self):
         self.assertEqual([0, 1, 2, 3, 4], knuth_morris_pratt("aaaaaaa", "aaa"))
         self.assertEqual([0, 4], knuth_morris_pratt("abcdabc", "abc"))
         self.assertEqual([], knuth_morris_pratt("aabcdaab", "aba"))
 
+
 if __name__ == "__main__":
     unittest.main()