题解 | 计算重复字符串长度

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    // 检查指定长度的子串是否存在重复
    bool hasRepeatedSubstring(const string& s, int len) {
        if (len == 0) return false;
        
        unordered_set<string> seen;
        // 使用滑动窗口检查所有可能的子串
        for (int i = 0; i <= s.length() - len; i++) {
            string sub = s.substr(i, len);
            if (seen.count(sub)) {
                return true;
            }
            seen.insert(sub);
        }
        return false;
    }
    
    int findMaxRepeatedLength(const string& s) {
        int maxLen = 0;
        // 枚举所有可能的子串长度
        for (int len = 1; len <= s.length() / 2; len++) {
            if (hasRepeatedSubstring(s, len)) {
                maxLen = len;
            }
        }
        return maxLen;
    }
};

int main() {
    string s;
    cin >> s;
    
    Solution solution;
    cout << solution.findMaxRepeatedLength(s) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        // 检查指定长度的子串是否存在重复
        private boolean hasRepeatedSubstring(String s, int len) {
            if (len == 0) return false;
            
            Set<String> seen = new HashSet<>();
            // 使用滑动窗口检查所有可能的子串
            for (int i = 0; i <= s.length() - len; i++) {
                String sub = s.substring(i, i + len);
                if (seen.contains(sub)) {
                    return true;
                }
                seen.add(sub);
            }
            return false;
        }
        
        public int findMaxRepeatedLength(String s) {
            int maxLen = 0;
            // 枚举所有可能的子串长度
            for (int len = 1; len <= s.length() / 2; len++) {
                if (hasRepeatedSubstring(s, len)) {
                    maxLen = len;
                }
            }
            return maxLen;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        Solution solution = new Solution();
        System.out.println(solution.findMaxRepeatedLength(s));
        
        sc.close();
    }
}

class Solution:
    def has_repeated_substring(self, s: str, length: int) -> bool:
        """检查指定长度的子串是否存在重复"""
        if length == 0:
            return False
        
        seen = set()
        # 使用滑动窗口检查所有可能的子串
        for i in range(len(s) - length + 1):
            sub = s[i:i + length]
            if sub in seen:
                return True
            seen.add(sub)
        return False
    
    def find_max_repeated_length(self, s: str) -> int:
        max_len = 0
        # 枚举所有可能的子串长度
        for length in range(1, len(s) // 2 + 1):
            if self.has_repeated_substring(s, length):
                max_len = length
        return max_len

def main():
    s = input().strip()
    solution = Solution()
    print(solution.find_max_repeated_length(s))

if __name__ == "__main__":
    main()