Repository: keon/algorithms
Pull request #575 (2019-10-23 15:20:47)

Manacher's algorithms - in Python 

- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?


Sean16SYSU: I have already fixed the conflicts.

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/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()