当前位置:网站首页>Simulation volume leetcode [general] 1062 Longest repeating substring
Simulation volume leetcode [general] 1062 Longest repeating substring
2022-07-06 06:17:00 【Encounter simulation volume】
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 !
边栏推荐
- 技术分享 | 常见接口协议解析
- On weak network test of special test
- 通过修改style设置打印页样式
- Redis 核心技术与实战之 基本架构:一个键值数据库包含什么?
- JWT-JSON WEB TOKEN
- [postman] test script writing and assertion details
- Coordinatorlayout+nestedscrollview+recyclerview pull up the bottom display is incomplete
- 在uni-app中使用腾讯视频插件播放视频
- Caused by:org.gradle.api.internal.plugins . PluginApplicationException: Failed to apply plugin
- Digital triangle model acwing 1015 Picking flowers
猜你喜欢
随机推荐
还在为如何编写Web自动化测试用例而烦恼嘛?资深测试工程师手把手教你Selenium 测试用例编写
数学三大核心领域概述:代数
模拟卷Leetcode【普通】1218. 最长定差子序列
【Postman】Monitors 监测API可定时周期运行
Properties file
php使用redis实现分布式锁
Seven imperceptible truths in software testing
B - The Suspects
Online and offline problems
(中)苹果有开源,但又怎样呢?
浅谈专项测试之弱网络测试
Request forwarding and redirection
Significance of unit testing
Buuctf-[bjdctf2020]zjctf, but so (xiaoyute detailed explanation)
10M25DCF484C8G(FPGA) AMY-6M-0002 BGA GPS模块
Full link voltage measurement: building three models
Buuctf-[gxyctf2019] no dolls (xiaoyute detailed explanation)
联合索引的左匹配原则
win10无法操作(删除、剪切)文件
MySQL之数据类型