Create repeated-substring-pattern.py

kamyu104 · web-flow · commit 0c0d8691433e · 2016-12-17T23:22:08.000+08:00
diff --git a/Python/repeated-substring-pattern.py b/Python/repeated-substring-pattern.py
@@ -0,0 +1,45 @@
+# Time:  O(n)
+# Space: O(n)
+
+# Given a non-empty string check if it can be constructed by taking a substring of it
+# and appending multiple copies of the substring together.
+# You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
+#
+# Example 1:
+# Input: "abab"
+#
+# Output: True
+#
+# Explanation: It's the substring "ab" twice.
+# Example 2:
+# Input: "aba"
+#
+# Output: False
+# Example 3:
+# Input: "abcabcabcabc"
+#
+# Output: True
+#
+# Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
+
+# KMP solution.
+class Solution(object):
+    def repeatedSubstringPattern(self, str):
+        """
+        :type str: str
+        :rtype: bool
+        """
+        def getPrefix(pattern):
+            prefix = [-1] * len(pattern)
+            j = -1
+            for i in xrange(1, len(pattern)):
+                while j > -1 and pattern[j + 1] != pattern[i]:
+                    j = prefix[j]
+                if pattern[j + 1] == pattern[i]:
+                    j += 1
+                prefix[i] = j
+            return prefix
+
+        prefix = getPrefix(str)
+        return prefix[-1] != -1 and \
+               (prefix[-1] + 1) % (len(str) - prefix[-1] - 1) == 0
