题目解析与代码实现：You‘re Given a String

引言

本文将详细解读一道字符串处理题目 “You’re Given a String”，并用 Python 实现该题的解决方案，同时解析其核心算法逻辑。本文适合有一定基础的程序员，希望通过字符串算法提升能力的读者。

---

1. 题目描述

问题背景

题目给出了一个字符串，要求找到字符串中长度最大的子串，使得该子串至少在字符串中出现两次。需要注意的是，这些子串可以重叠。

输入与输出

输入：

• 一个字符串，长度不超过 100，包含小写拉丁字母，且非空。

输出：

• 一个整数，表示满足条件的最长子串的长度。如果没有子串满足要求，输出 0。

题目保证：

• 字符串一定是小写字母构成。
• 字符串长度不超过 100。

示例

下面是几个输入与输出示例：

输入	输出
abcd	0
ababa	3
zzz	2

---

2. 题目分析

这是一道经典的字符串处理问题，重点在于 如何高效地判断某个子串是否至少出现了两次。根据题目要求和示例，可以发现如下几个特点：

1. 子串长度越大，越难出现至少两次。我们可以从长到短依次检测。
2. 使用集合（Set）可以高效地检测子串是否重复。
3. 暴力解法的时间复杂度约为 O(n3)O(n^3)，需要优化。

---

核心算法设计

1. 子串枚举

子串可以用长度 length 和起点 start 唯一确定，子串的计算方式为 input[start:start + length]。对于每个长度 length，我们枚举所有可能的起点 start。

2. 用集合检测重复

通过集合（Set）存储已经出现的子串：

• 如果当前子串没有出现在集合中，将其加入集合。
• 如果当前子串已经存在，说明该子串至少出现了两次，直接返回该长度。

3. 提前退出

我们从最大长度（即字符串长度 - 1）开始检查，一旦发现满足条件的子串，可以提前退出循环，不再继续检查更短的子串。

---

3. Python 实现

以下是题目的 Python 实现：

def main():input_string = input().strip()output = 0# 枚举子串长度，从大到小for length in range(len(input_string) - 1, 0, -1):if output > 0:  # 如果找到结果，提前退出breakpresent = set()# 枚举起点，计算子串for start in range(len(input_string) - length + 1):current = input_string[start:start + length]if current not in present:present.add(current)  # 将当前子串加入集合else:output = length  # 找到满足条件的子串，记录长度breakprint(output)  # 输出结果if __name__ == "__main__":main()

---

代码解读

• 使用 Python 的字符串切片 input_string[start:start + length] 替代了 C++ 的 substr。
• 用 Python 的集合 set 代替了 C++ 的 std::set。
• 外层循环控制子串长度，内层循环枚举起点，逻辑完全一致。

---

4. 示例测试

下面是对代码的实际测试：

测试 1：abcd

• 输入：abcd
• 预期输出：0
• 解释：字符串中没有重复的子串。

测试 2：ababa

• 输入：ababa
• 预期输出：3
• 解释：子串 aba 是最长的满足条件的子串，长度为 3。

测试 3：zzz

• 输入：zzz
• 预期输出：2
• 解释：子串 zz 是最长的满足条件的子串，长度为 2。

---

5. 算法复杂度分析

时间复杂度

外层循环的复杂度为 O(n)O(n)，内层循环复杂度为 O(n)O(n)，每次检查子串是否在集合中的复杂度为 O(1)O(1)。总时间复杂度为：

O(n2)O(n^2)

空间复杂度

主要使用了集合存储子串，空间复杂度为 O(n)O(n)。

---

6. 小结

本文通过 Python 实现了这道经典字符串问题的解决方案。通过枚举子串长度并利用集合检测重复，我们实现了一个高效的算法，能够处理长度不超过 100 的字符串。

希望本文对你在字符串算法的学习中有所帮助！

---

附录：完整代码

def main():input_string = input().strip()output = 0for length in range(len(input_string) - 1, 0, -1):if output > 0:breakpresent = set()for start in range(len(input_string) - length + 1):current = input_string[start:start + length]if current not in present:present.add(current)else:output = lengthbreakprint(output)if __name__ == "__main__":main()

---

这篇文章带你从问题分析到完整代码实现，希望能让你对字符串处理问题有更深刻的理解！如果觉得有帮助，记得点赞和收藏哦！