Участник:F.Nikitin/LongestDuplicateSubstring

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/longest-duplicate-substring/

from functools import reduce
 
class Solution:
    def longestDupSubstring(self, S):
        n_latin = 26
        num_string = [ord(char) - ord('a') for char in S]
        mod = 2**63 - 1
 
        def test(length):
            p = pow(n_latin, length, mod)
            cur = reduce(lambda x, y: (x * n_latin + y) % mod, num_string[:length], 0)
            seen = {cur}
            for i in range(length, len(S)):
                cur = (cur * n_latin + num_string[i] - num_string[i - length] * p) % mod
                if cur in seen:
                    return i - length + 1
                seen.add(cur)
 
        res, lo, hi = 0, 0, len(S)
        while lo < hi:
            mi = (lo + hi + 1) // 2
 
            pos = test(mi)
            if pos:
                lo = mi
                res = pos
            else:
                hi = mi - 1
        return S[res:res + lo]