当前位置:网站首页>模拟卷Leetcode【普通】1062. 最长重复子串
模拟卷Leetcode【普通】1062. 最长重复子串
2022-07-06 06:15:00 【邂逅模拟卷】
汇总:模拟卷Leetcode 题解汇总
1062. 最长重复子串
给定字符串 S,找出最长重复子串的长度。如果不存在重复子串就返回 0。
示例 1:
输入:“abcd”
输出:0
解释:没有重复子串。
示例 2:
输入:“abbaba”
输出:2
解释:最长的重复子串为 “ab” 和 “ba”,每个出现 2 次。
示例 3:
输入:“aabcaabdaab”
输出:3
解释:最长的重复子串为 “aab”,出现 3 次。
示例 4:
输入:“aaaaa”
输出:4
解释:最长的重复子串为 “aaaa”,出现 2 次。
提示:
字符串 S 仅包含从 ‘a’ 到 ‘z’ 的小写英文字母。
1 <= S.length <= 1500
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-repeating-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
代码:
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转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')
备注:
GitHub:https://github.com/monijuan/leetcode_python
CSDN汇总:模拟卷Leetcode 题解汇总
可以加QQ群交流:1092754609
leetcode_python.utils详见汇总页说明
先刷的题,之后用脚本生成的blog,如果有错请留言,我看到了会修改的!谢谢!
边栏推荐
- RestTemplate、Feign实现Token传递
- Linux regularly backs up MySQL database
- Still worrying about how to write web automation test cases? Senior test engineers teach you selenium test case writing hand in hand
- 自定义指定路由上的Gateway过滤器工厂
- Customize the gateway filter factory on the specified route
- [postman] collections - run the imported data file of the configuration
- Buuctf-[gxyctf2019] no dolls (xiaoyute detailed explanation)
- Seven imperceptible truths in software testing
- php使用redis实现分布式锁
- selenium源码通读·9 |DesiredCapabilities类分析
猜你喜欢
随机推荐
Construction and integration of Zipkin and sleuth for call chain monitoring
Still worrying about how to write web automation test cases? Senior test engineers teach you selenium test case writing hand in hand
【Postman】Collections-运行配置之导入数据文件
VINS-Mono: A Robust and Versatile Monocular Visual-Inertial State Estimator
10M25DCF484C8G(FPGA) AMY-6M-0002 BGA GPS模块
GTSAM中李群的运用
Manhattan distance and Manhattan rectangle - print back font matrix
异常检测方法总结
Cannot create PoolableConnectionFactory (Could not create connection to database server. 错误
RestTemplate、Feign实现Token传递
Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
功能安全之故障(fault),错误(error),失效(failure)
Database - current read and snapshot read
误差的基本知识
LeetCode 739. 每日温度
Idea new UI usage
假设检验学习笔记
Overview of three core areas of Mathematics: geometry
Application du Groupe Li dans gtsam
【Postman】Collections配置运行过程