[LeetCode] Repeated Substring Pattern 파이썬 (KMP)

문제 풀이하기전에 KMP 알고리즘이 무엇인지 알아보자

 

이 문제를 Brute Force로 풀면 풀리긴 하지만.

O(n*m)의 문제를 O(n)으로 풀 수 있는 KMP 알고리즘으로 풀어보자

 

알고리즘 자체는 어렵지 않지만

설명이 어쩔 수 없이 길어지는 알고리즘이다.

 

요약:

LPS 라는 table을 생성 ( Longest Prefix and also Suffix )

LPS 테이블을 활용해서 이미 searched된 pattern은 skip.

LPS 테이블에서 0이 아닌 sub-pattern부터 탐색 가능하기 때문에 효율적인 방식.

 

 

---

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

    def repeatedSubstringPattern2(self, str):
        """
        :type str: str
        :rtype: bool
        """
        if not str:
            return False

        ss = (str + str)[1:-1]
        print(ss)
        return ss.find(str) != -1

출처: github.com/jiapengwen/LeetCode/blob/master/Python/repeated-substring-pattern.py

 

---

KMP

참고자료:

1. www.youtube.com/watch?v=4jY57Ehc14Y 

2. www.youtube.com/watch?v=BXCEFAzhxGY

 

bowbowbow.tistory.com/6