中天建设集团有限公司总网站应式网站
引言
本文将详细解读一道字符串处理题目 “You’re Given a String”，并用 Python 实现该题的解决方案，同时解析其核心算法逻辑。本文适合有一定基础的程序员，希望通过字符串算法提升能力的读者。
1. 题目描述
问题背景
题目给出了一个字符串，要求找到字符串中长度最大的子串，使得该子串至少在字符串中出现两次。需要注意的是，这些子串可以重叠。
输入与输出
输入：
- 一个字符串，长度不超过 100，包含小写拉丁字母，且非空。
输出：
- 一个整数，表示满足条件的最长子串的长度。如果没有子串满足要求，输出 0。
题目保证：
- 字符串一定是小写字母构成。
- 字符串长度不超过 100。
示例
下面是几个输入与输出示例：
| 输入 | 输出 |
|---|---|
abcd | 0 |
ababa | 3 |
zzz | 2 |
2. 题目分析
这是一道经典的字符串处理问题，重点在于 如何高效地判断某个子串是否至少出现了两次。根据题目要求和示例，可以发现如下几个特点：
- 子串长度越大，越难出现至少两次。我们可以从长到短依次检测。
- 使用集合（Set）可以高效地检测子串是否重复。
- 暴力解法的时间复杂度约为 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()
这篇文章带你从问题分析到完整代码实现，希望能让你对字符串处理问题有更深刻的理解！如果觉得有帮助，记得点赞和收藏哦！