Longest Duplicate Substring

제목

폭력법

python 코드

이분법+Rabin-Karp

python 코드

제목.

Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times. (The occurrences may overlap.)
Return any duplicated substring that has the longest possible length. (If S does not have a duplicated substring, the answer is “”.)
Example 1:
Input: “banana” Output: “ana”
Example 2:
Input: “abcd” Output: “”
Note:
2 <= S.length <= 10^5 S consists of lowercase English letters.

폭력법

면접을 볼 때 이 문제를 만났습니다. 그리고 처음에 주의하지 않았습니다. 최장남열을 구하는 줄 알았습니다. 최장남열을 구하는 사고방식을 말한 후에 시험관은 최장중복자열을 구한다고 했습니다. 그런데 동태 계획을 하려고 했지만 상태 방정식을 찾지 못했습니다. 그리고 가장 간단한 빈거법을 생각했습니다. 면접관이 힌트를 주었는데 마지막에 쓰지 못했습니다. 아마 면접을 끊었을 것입니다.
왜 면접을 볼 때 머리가 텅 비었는지 모르겠지만 내려와서 스스로 생각을 정리한 후에 폭력법도 해결할 수 있다. 제목이 준 예는 통과할 수 있지만 결국 시간이 초과되었다.
사고방식은 사실 매우 간단하다. 서브열을 1에서 n까지 하나하나 비교한다.한 자모로 훑어보기 시작하여 어느 자열의 중복수가 가장 큰지 봅시다. b, a, n, a, n, a, 한 문자는'a'의 중복수가 가장 크고 이를 한 수조에 저장합니다.그리고 두 문자의, ba, an, na, an, na를 보고 'an' 을 그룹에 저장합니다.

python 코드

class Solution(object):
    def longestDupSubstring(self, S):
        """
        :type S: str
        :rtype: str
        """
        if not S:
            return ""
        res = []
        n = len(S)
        j = 1
        while j < n:
            d = dict()
            for i in range(n):
                k = i + j
                if k < n+1:
                    if S[i:k] in d:
                        d[S[i:k]] += 1
                    else:
                        d[S[i:k]] = 1
            mmax = 1
            for k, v in d.items():
                if v > mmax:
                    mmax = v
                    temp = k
            if mmax > 1:
                res.append(temp)
            else:
                res.append("")
            j += 1

        c = 0
        for s in res:
            if len(s) >= c:
                c = len(s)
                t = s
        return t

시간의 복잡도는 O(n^2)이고 공간의 복잡도는 O(n)이다.

이분법+Rabin-Karp

Rabin-Karp 알고리즘은 문자열 검색의 일종으로 문자열을 해시 값으로 바꾸어 계산한 다음에 알파벳의 값을 빼고 알파벳의 값을 더해서 중복되는지 비교하는 것이다.예를 들어 128진법의'bbc'를 계산한다. b* 128^2 + b* 128^1 + c= 1605632 + 12544 + 99 = 1618275를 계산한 다음에 첫 번째 b: - b* 128^2를 빼고 한 자리를 뒤로 이동한다. * 128, 그리고 마지막 자모, 즉 (1618275 - b* 128^2)* 128 + x의 값을 빼고 6447715(bbc)와 비교한다.이런 계산 방식도'롤링 해시'라고 부른다.

python 코드

class Solution(object):
    def longestDupSubstring(self, S):
        """
        :type S: str
        :rtype: str
        """
        def search(m,MOD):
            h = 0
            for i in range(m):
                h = (h*26+nums[i])%MOD
            s = {h}
            aL = pow(26,m,MOD)
            for pos in range(1,n-m+1):
                h = (h*26-nums[pos-1]*aL+nums[pos+m-1])%MOD
                if h in s:
                    return pos
                s.add(h)
            return -1
            
        if not S:
            return ""
        n = len(S)
        nums = [ord(c)-ord('a') for c in S]
        l = 1
        r = n
        pos = 0
        MOD = 2**63 -1
        while l <= r:
            m = (l+r)//2
            cur = search(m,MOD)
            if cur!=-1:
                l = m+1
                pos = cur
            else:
                r = m-1
        return S[pos:pos+l-1]

시간의 복잡도는 O(nlogn)이고 공간의 복잡도는 O(n)이다.