欢迎访问宙启技术站
智能推送

如何编写Java函数来查找两个字符串之间的最长公共子串?

发布时间:2023-07-01 04:25:17

要编写一个Java函数来查找两个字符串之间的最长公共子串,可以使用动态规划的方法来解决这个问题。下面是一种可以实现这个功能的Java函数的伪代码。

public String findLongestCommonSubstring(String str1, String str2) {
    // 创建一个二维数组来记录公共子串的长度
    int[][] dp = new int[str1.length() + 1][str2.length() + 1];

    // 记录最长公共子串的长度和起始位置
    int maxLength = 0;
    int end = 0;

    // 遍历两个字符串,计算公共子串的长度
    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            // 如果当前字符相同,公共子串的长度加1
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;

                // 更新最长公共子串的长度和结束位置
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    end = i - 1;
                }
            }
        }
    }

    // 根据最长公共子串的长度和结束位置,获取最长公共子串
    String longestCommonSubstring = str1.substring(end - maxLength + 1, end + 1);

    return longestCommonSubstring;
}

这个函数的时间复杂度为O(m*n),其中m和n分别是两个字符串的长度。在函数中,我们创建一个二维数组dp来记录公共子串的长度。然后,我们遍历两个字符串,如果当前字符相同,就将公共子串的长度加1,并更新最长公共子串的长度和结束位置。最后,根据最长公共子串的长度和结束位置,获取最长公共子串。

需要注意的是,这个函数只能找到两个字符串中最长的公共子串,但是无法找到所有的公共子串。如果需要找到所有的公共子串,可以使用回溯法或者其他方法来解决。