最长重复子串及其下标位置数据结构算法代码加详细过程

最长重复子串（Longest Repeated Substring）问题是指在一个字符串中找到重复出现次数最多的子串，并返回该子串以及它的起始下标。这个问题通常可以用滑动窗口（Sliding Window）的数据结构和动态规划（Dynamic Programming）的思想来解决。

下面是Python的一个简单实现：

def longest_repeated_substring(s):
    if not s:
        return "", -1

    length = len(s)
    # 使用两个哈希集合存储当前和前一窗口内的字符
    window_set, prev_window_set = set(), set()

    max_len = 1
    start = 0
    for i in range(length):
        # 如果当前字符已经在前一个窗口内，则说明找到了重复子串
        if s[i] in prev_window_set:
            # 更新最大长度和起点
            cur_len = i - prev_window_set[s[i]]
            if cur_len > max_len:
                max_len = cur_len
                start = prev_window_set[s[i]] + 1
        # 将当前字符添加到窗口集合中，移除窗口左侧已超出部分
        prev_window_set.remove(s[start])
        window_set.add(s[i])

        # 如果窗口右侧有新的字符，将其添加到窗口集合中
        if i >= max_len:
            prev_window_set.add(s[start])

    # 返回最长重复子串和起始下标
    return s[start:start+max_len], start


# 测试例子
s = "banana"
sub, index = longest_repeated_substring(s)
print(f"最长重复子串是 '{sub}'，位于索引 {index}")

在这个代码中，我们用一个滑动窗口从左到右遍历输入字符串`s`。窗口内的每个字符都在一个集合中维护，当遇到重复字符时，就更新最长重复子串的长度和起始位置。如果窗口移动过程中有新的字符加入，我们就移除窗口左侧的第一个字符。这样做的目的是保持窗口内字符的独特性，从而快速查找重复字符。