利用 C++ 解决录音笔线索查找最长重复子串问题

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <string> #include <vector> #include <algorithm> // 检查长度为 len 的子串是否至少出现两次 bool check(const std::string& s, int len) { int n = s.length(); std::vector<std::string> substrings; // 遍历字符串，提取所有长度为 len 的子串 for (int i = 0; i <= n - len; ++i) { substrings.push_back(s.substr(i, len)); } // 对提取的子串进行排序 std::sort(substrings.begin(), substrings.end()); // 检查是否有重复的子串 for (int i = 1; i < substrings.size(); ++i) { if (substrings[i] == substrings[i - 1]) { return true; } } return false; } // 主函数 int main() { std::string s; std::cin >> s; int n = s.length(); int left = 0, right = n; int result = 0; // 二分查找最长子串的长度 while (left <= right) { int mid = left + (right - left) / 2; if (check(s, mid)) { result = mid; left = mid + 1; } else { right = mid - 1; } } std::cout << result << std::endl; return 0; } ``` ### 代码解释： 1. **`check` 函数**：该函数用于检查长度为 `len` 的子串是否至少出现两次。它通过遍历字符串，提取所有长度为 `len` 的子串，并将这些子串存储在 `substrings` 向量中。然后对 `substrings` 向量进行排序，检查是否有重复的子串。 2. **主函数**： - 读取输入的字符串。 - 使用二分查找来确定最长子串的长度。 - 二分查找的左边界 `left` 初始化为 0，右边界 `right` 初始化为字符串的长度。 - 在二分查找的过程中，调用 `check` 函数检查当前的中间长度 `mid` 是否满足条件。如果满足条件，则更新结果 `result` 并将左边界 `left` 更新为 `mid + 1`；否则，将右边界 `right` 更新为 `mid - 1`。 3. **输出结果**：最终输出至少出现两次的最长子串的长度。 ######[AI问答 | 634点数解答 | 2026-03-29 15:45:29]