Java实现求两个字符串最长公共子串长度

问题背景与规则

求两个字符串的最长公共子串（Longest Common Substring）是常见的字符串处理问题。在华为在线评测系统（OJ）上提交Java代码时，需严格遵守以下规则以确保编译与运行通过：

1. 不允许包含包名（package声明）。
2. 主类名必须固定为 Main。
3. 仅输出最终结果，禁止打印任何调试信息或过程提示。

算法思路

该实现采用暴力遍历法。首先将输入的两个字符串统一转为小写，以忽略大小写差异。接着，通过三层循环结构进行匹配检查：外层循环控制子串长度 i，由大到小递减；中间层循环控制较短字符串 min 的起始位置 j；内层循环控制较长字符串 max 的起始位置 k。一旦发现匹配子串，立即返回当前长度 i。

第1步：定义标准主类入口

在华为OJ环境中，直接编写带 Main 类的程序。使用 Scanner 读取两行输入，调用核心方法后输出整数结果。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入的两个字符串
        String str1 = sc.next();
        String str2 = sc.next();
        
        // 获取公共子串长度并打印
        int len = getCommonStrLength(str1, str2);
        System.out.println(len);
    }
}

第2步：实现核心匹配逻辑

核心方法接收两个字符串参数，先执行大小写转换和长度对比，再通过嵌套循环寻找最大共同子串长度。

    int getCommonStrLength(String str1, String str2) {
        // 1. 统一转为小写，忽略大小写影响
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        int len1 = str1.length();
        int len2 = str2.length();
        
        // 2. 确定长短串，优化后续遍历范围
        String min = (len1 <= len2) ? str1 : str2;
        String max = (len1 > len2) ? str1 : str2;
        
        // 3. 从最长可能长度开始向下查找
        for (int i = min.length(); i >= 1; i--) {
            // 4. 遍历短串的所有长度为i的子串
            for (int j = 0; j <= min.length() - i; j++) { 
                String target = min.substring(j, j + i); 
                
                // 5. 在长串中查找是否存在相同子串
                for (int k = 0; k <= max.length() - i; k++) { 
                    if (max.substring(k, k + i).equals(target)) { 
                        return i; // 找到即返回当前长度，即为最大长度
                    }
                }
            }
        } 
        // 6. 若无公共子串，返回0
        return 0; 
    }

代码注意事项

上述代码虽然逻辑清晰且能正确解决问题，但时间复杂度较高，属于 O(N^3) 级别的暴力解法。在实际开发或更高级别的算法竞赛中，通常建议采用动态规划（Dynamic Programming）方法将复杂度优化至 O(N*M)。但在应对此类基础OJ题目时，此写法足以满足测试用例要求且易于理解。

以上就是Java实现求两个字符串最长公共子串长度的详细内容，更多关于Java算法设计的资料请关注本站其它相关文章！