使用python,如何实现以下问题
给定一个数组,求该数组中最长重复子数组(每个子数组间不重叠),输出第一个子数组的起始下标与长度、并将该数组输出,要求程序的时间复杂度小于等于O(nlogn)
程序示例
示例1
输入:[1,2,3,4,5,7,2,3,4,5]
输出:
起始下标:1
长度:4
重复子数组:[2,3,4,5]
示例2
输入:[0,1,1,1,1]
输出:
起始下标:1
长度:2
重复子数组:[1,1]
使用python,如何实现以下问题
给定一个数组,求该数组中最长重复子数组(每个子数组间不重叠),输出第一个子数组的起始下标与长度、并将该数组输出,要求程序的时间复杂度小于等于O(nlogn)
程序示例
示例1
输入:[1,2,3,4,5,7,2,3,4,5]
输出:
起始下标:1
长度:4
重复子数组:[2,3,4,5]
示例2
输入:[0,1,1,1,1]
输出:
起始下标:1
长度:2
重复子数组:[1,1]
最长重复子数组长度肯定小于等于len/2,暴力循环求解
n=eval(input())
def search(n):
for i in range(int(len(n) / 2), 0, -1):
for j in range(int(len(n) / 2)):
for h in range(j + i, len(n) - i + 1):
if n[j:j + i] == n[h:h + i]:
print('起始下标:',j)
print('长度:',i)
print('重复子数组:',n[j:j + i])
return
search(n)