iT邦幫忙

3

【小馬的LeetCode練功坊】(相當難!) 1044題- 最長的重複字串,用RabinKarp算法做字串匹配

嗨,大家好,
分享自己這幾天練leetcode碰到的一道難題

參考題目:1044. Longest Duplicate Substring
題意: 給定一個字串,回傳最長的子字串使得子字串至少在原字串中出現兩次
例如:

Input: "banana"
Output: "ana" (在index1,3各出現一次)

這一題看起來實現沒有頭緒,
好在題目給了兩個提示:

  1. 對子字串的長度做二分搜索,因為如果存在長度k的子字串滿足條件,那一定存在長度k-1,k-2,...,1的字串滿足條件
  2. 用Rabin-Karp演算法判斷長度k的子字串是否出現2次

Rabin-Karp演算法?
沒聽過,所以小馬先嘗試看看不用這個演算法有沒有辦法解。

嘗試- 搜索子字串是否再後面出現,超時

這個是我在研究Rabin-Karp演算法前的嘗試,
對於字串長度M的情形,
窮舉所有可能的子字串,
直接用字串內建函數看它在後面是否出現

我分析時間大概是O(n^2*log n) (其中log n來自二分搜索的時間),
不負眾望的超時了

class Solution:
    def mySearch(self, text, M):
        for i in range(len(text) - M):
            if(text.find(text[i:i+M], i+1)!=-1):
                return (True, text[i:i+M])
        return (False, "")

    def longestDupSubstring(self, S: str) -> str:
        beg, end = 0, len(S)
        Found = ""
        while beg + 1 < end:
            mid = (beg + end)//2
            isFound, candidate = self.mySearch(S, mid)
            if isFound:
                beg, Found = mid, candidate
            else:
                end = mid
        return Found

AC- Rabin-Karp演算法 + 二分搜索

Rabin-Karp演算法是一個字串匹配算法,
解說可參考leetcode上的解說wiki
原理: 對於子字串,我們可以計算它的hash value,
例如abc 的 hash value為 (ord('a')*d^2 + ord('b')*d^1 + ord('c')*d^0) % q
bac 的 hash value為 (ord('b')*d^2 + ord('a')*d^1 + ord('c')*d^0) % q
d可以想成是「d進位」的意思(選d=256即可,因為ord('z')比256小),
q選擇一個大質數,
%q是避免hash value過大

至此有兩種思維處理hash value相同的情形,

  1. 有可能原始字串不同達到相同的hash value,因此要檢查子字串是否相同 (保證正確性)
  2. 選擇一個超大的質數q,使得不同字串但hash value相同的機率低,只要hash value相同就直接當做字串相同(不一定永遠正確但快速)

分別演示兩種做法,時間大概是O(n*log n),
因為可以用O(1)的時間取得下一個子字串的hash value:

解法一、保證正確但較慢(ac, 2448ms)

class Solution:
    
    def RabinKarp(self,text, M, q):
        if M == 0: 
            return True
        hashVal, base = 0, 256
        shift = (base ** (M-1)) % q

        dic = defaultdict(list)

        for i in range(M): 
            hashVal= (base * hashVal + ord(text[i]))% q

        dic[hashVal].append(i-M+1)

        for i in range(1,len(text) - M +1):
            hashVal = (base*(hashVal-ord(text[i-1])*shift) + ord(text[i + M -1]))% q
            for j in dic[hashVal]:
                if text[i:i+M] == text[j:j+M]:
                    return (True, text[j:j+M])
            dic[hashVal].append(i)
        return (False, "")


    def longestDupSubstring(self, S:str) ->str:
        beg, end = 0, len(S)
        q = (1<<31) - 1 
        Found = ""
        while beg + 1 < end:
            mid = (beg + end)//2
            isFound, candidate = self.RabinKarp(S, mid, q)
            if isFound:
                beg, Found = mid, candidate
            else:
                end = mid
        return Found

解法二、不一定永遠正確但快速(ac, 1804ms)

class Solution:
    
    def RabinKarp(self,text, M, q):
        if M == 0: 
            return True
        hashVal, base = 0, 256
        shift = (base ** (M-1)) % q

        dic = defaultdict(lambda x:0)

        for i in range(M): 
            hashVal= (base * hashVal + ord(text[i]))% q

        dic[hashVal] = i-M+1

        for i in range(1,len(text) - M +1):
            hashVal = (base*(hashVal-ord(text[i-1])*shift) + ord(text[i + M -1]))% q
            if hashVal in dic:
                return (True, text[i:i+M])
            dic[hashVal] = i
        return (False, "")


    def longestDupSubstring(self, S:str) ->str:
        beg, end = 0, len(S)
        q = 35184372088891 #隨意找的大質數
        Found = ""
        while beg + 1 < end:
            mid = (beg + end)//2
            isFound, candidate = self.RabinKarp(S, mid, q)
            if isFound:
                beg, Found = mid, candidate
            else:
                end = mid
        return Found
        

尚未有邦友留言

立即登入留言