求列表中最长重复子序列及原、重复序列的起始索引

我的代码只能检测单个重复元素，无法识别完整的重复子序列。需要实现的功能是：从输入列表中找出最长的重复子序列，同时输出三个值：

• 该子序列的长度
• 它在原序列中首次出现的起始索引
• 它重复出现的首个起始索引

示例：

• 输入：1 2 3 3 3 3 3 3 3 3 5 6 → 输出：4 2 6
• 输入：1 2 3 4 5 6 5 7 8 9 → 输出：1 4 6

现有代码 #

input = list(map(int, input().split()))
duple = []
new  = []
lenght = 0
same_duple = []
for elem in input:
    if elem in new:
        duple.append(elem)
    else:
        new.append(elem)

if duple[0] in input:
    index_first = input.index(duple[0]) 

if len(duple) > 1:
    if len(set(duple)) == 1:
        duple.append(duple[0]) 
        lenght = len(duple)//2
        index_sec = (len(input) - list(reversed(input)).index(duple[lenght])-lenght)
        #index_sec = (len(input) - list(reversed(input)).index(same_duple[0])-1)
        #index_sec = next((idx for idx, item in enumerate(input) if item in input[:idx]), None)
    else:
        lenght = len(duple)
        index_sec = (len(vstup) - list(reversed(input)).index(duple[0])-1)
else:
        lenght = len(duple)
        index_sec = (len(vstup) - list(reversed(input)).index(duple[0])-1)

print(lenght)
print(index_first)
print(index_sec)

现有代码的问题 #

1. 逻辑仅针对单个重复元素，完全没有处理「子序列重复」的场景，无法识别连续重复的子序列
2. 存在未定义变量vstup，运行会直接报错
3. 索引计算逻辑混乱，仅对全相同的重复元素有部分效果，不具备通用性
4. 没有对比不同重复子序列的长度，无法找到最长的那一个

解决方案代码 #

def find_longest_duplicate_subseq(arr):
    n = len(arr)
    max_len = 0
    first_idx = -1
    repeat_idx = -1

    # 从最长可能的子序列长度开始遍历，找到第一个符合条件的就返回（保证最长）
    for length in range(n//2, 0, -1):
        seen = {}
        for i in range(n - length + 1):
            # 用元组存储子序列，因为列表不能作为字典键
            subseq = tuple(arr[i:i+length])
            if subseq in seen:
                max_len = length
                first_idx = seen[subseq]
                repeat_idx = i
                return max_len, first_idx, repeat_idx
            else:
                seen[subseq] = i
    # 没有找到长度≥2的重复子序列，找第一个重复的单个元素
    seen = {}
    for idx, num in enumerate(arr):
        if num in seen:
            return 1, seen[num], idx
        seen[num] = idx
    # 完全没有重复元素的边界情况
    return 0, -1, -1

# 处理输入输出
input_arr = list(map(int, input().split()))
length, first, repeat = find_longest_duplicate_subseq(input_arr)
print(length)
print(first)
print(repeat)

代码说明 #

1. 核心逻辑：从最长的可能子序列长度（数组长度的一半，因为子序列至少要出现两次）开始遍历，用字典记录每个子序列首次出现的索引，一旦发现重复就立即返回，确保找到的是最长的重复子序列
2. 子序列存储：用tuple作为字典的键（列表无法哈希），存储每个连续子序列的起始索引
3. 边界处理：如果没有找到长度≥2的重复子序列，自动退而寻找第一个重复的单个元素，匹配示例中的第二个输入场景
4. 输出匹配：直接返回需求的三个值，按要求打印

内容的提问来源于stack exchange，提问作者Mark