手機端網(wǎng)站重構seo下拉優(yōu)化
引言
本文將詳細解讀一道字符串處理題目 “You’re Given a String”，并用 Python 實現(xiàn)該題的解決方案，同時解析其核心算法邏輯。本文適合有一定基礎的程序員，希望通過字符串算法提升能力的讀者。
1. 題目描述
問題背景
題目給出了一個字符串，要求找到字符串中長度最大的子串，使得該子串至少在字符串中出現(xiàn)兩次。需要注意的是，這些子串可以重疊。
輸入與輸出
輸入：
- 一個字符串，長度不超過 100，包含小寫拉丁字母，且非空。
輸出：
- 一個整數(shù)，表示滿足條件的最長子串的長度。如果沒有子串滿足要求，輸出 0。
題目保證：
- 字符串一定是小寫字母構成。
- 字符串長度不超過 100。
示例
下面是幾個輸入與輸出示例：
| 輸入 | 輸出 |
|---|---|
abcd | 0 |
ababa | 3 |
zzz | 2 |
2. 題目分析
這是一道經(jīng)典的字符串處理問題，重點在于 如何高效地判斷某個子串是否至少出現(xiàn)了兩次。根據(jù)題目要求和示例，可以發(fā)現(xiàn)如下幾個特點：
- 子串長度越大，越難出現(xiàn)至少兩次。我們可以從長到短依次檢測。
- 使用集合（Set）可以高效地檢測子串是否重復。
- 暴力解法的時間復雜度約為 O(n3)O(n^3)，需要優(yōu)化。
核心算法設計
1. 子串枚舉
子串可以用長度 length 和起點 start 唯一確定，子串的計算方式為 input[start:start + length]。對于每個長度 length，我們枚舉所有可能的起點 start。
2. 用集合檢測重復
通過集合（Set）存儲已經(jīng)出現(xiàn)的子串：
- 如果當前子串沒有出現(xiàn)在集合中，將其加入集合。
- 如果當前子串已經(jīng)存在，說明該子串至少出現(xiàn)了兩次，直接返回該長度。
3. 提前退出
我們從最大長度（即字符串長度 - 1）開始檢查，一旦發(fā)現(xiàn)滿足條件的子串，可以提前退出循環(huán)，不再繼續(xù)檢查更短的子串。
3. Python 實現(xiàn)
以下是題目的 Python 實現(xiàn)：
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。 - 外層循環(huán)控制子串長度，內(nèi)層循環(huán)枚舉起點，邏輯完全一致。
4. 示例測試
下面是對代碼的實際測試：
測試 1：abcd
- 輸入：
abcd - 預期輸出：
0 - 解釋：字符串中沒有重復的子串。
測試 2：ababa
- 輸入：
ababa - 預期輸出：
3 - 解釋：子串
aba是最長的滿足條件的子串，長度為 3。
測試 3：zzz
- 輸入：
zzz - 預期輸出：
2 - 解釋：子串
zz是最長的滿足條件的子串，長度為 2。
5. 算法復雜度分析
時間復雜度
外層循環(huán)的復雜度為 O(n)O(n)，內(nèi)層循環(huán)復雜度為 O(n)O(n)，每次檢查子串是否在集合中的復雜度為 O(1)O(1)。總時間復雜度為：
O(n2)O(n^2)
空間復雜度
主要使用了集合存儲子串，空間復雜度為 O(n)O(n)。
6. 小結
本文通過 Python 實現(xiàn)了這道經(jīng)典字符串問題的解決方案。通過枚舉子串長度并利用集合檢測重復，我們實現(xiàn)了一個高效的算法，能夠處理長度不超過 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()
這篇文章帶你從問題分析到完整代碼實現(xiàn)，希望能讓你對字符串處理問題有更深刻的理解！如果覺得有幫助，記得點贊和收藏哦！