Simulation volume leetcode [general] 1062 Longest repeating substring

Summary ： Simulation volume Leetcode Summary of questions

1062. Longest repeated substring

Given string  S, Find the length of the longest repeating substring . If there is no duplicate substring, it returns 0.

Example 1：

Input ：“abcd”
Output ：0
explain ： No repeating substrings .
Example 2：

Input ：“abbaba”
Output ：2
explain ： The longest repeating substring is “ab” and “ba”, Each occurrence 2 Time .
Example 3：

Input ：“aabcaabdaab”
Output ：3
explain ： The longest repeating substring is “aab”, appear 3 Time .
Example 4：

Input ：“aaaaa”
Output ：4
explain ： The longest repeating substring is “aaaa”, appear 2 Time .

Tips ：

character string  S  Only from  ‘a’ To  ‘z’  Small English letters .
1 <= S.length <= 1500

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/longest-repeating-substring
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def search(self, L: int, a: int, modulus: int, n: int, nums: List[int]) -> str:
        """ Rabin-Karp with polynomial rolling hash. Search a substring of given length that occurs at least 2 times. @return start position if the substring exits and -1 otherwise. """
        # compute the hash of string S[:L]
        h = 0
        for i in range(L):
            h = (h * a + nums[i]) % modulus

        # already seen hashes of strings of length L
        seen = {
    h}
        # const value to be used often : a**L % modulus
        aL = pow(a, L, modulus)
        for start in range(1, n - L + 1):
            # compute rolling hash in O(1) time
            h = (h * a - nums[start - 1] * aL + nums[start + L - 1]) % modulus
            if h in seen:
                return start
            seen.add(h)
        return -1

    def longestRepeatingSubstring(self, S: str) -> str:
        n = len(S)
        # convert string to array of integers
        # to implement constant time slice
        nums = [ord(S[i]) - ord('a') for i in range(n)]
        # base value for the rolling hash function
        a = 26
        # modulus value for the rolling hash function to avoid overflow
        modulus = 2 ** 24

        # binary search, L = repeating string length
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search(L, a, modulus, n, nums) != -1:
                left = L + 1
            else:
                right = L - 1

        return left - 1


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.getResult(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！