寻找两个字符串中的最大公串

算法1：

循环生成第一个字符串的所有子串，按从大到小的顺序在第二个字符串中查找这些子串，找到即返回。

 

public String maxMutualStr(String str1, String str2)
{
    int len = str1.length();
    for (int i = 0; i < len; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            String tmp = str1.substring(i, len - j);
            if (str2.contains(tmp)) return tmp;
        }
    }

    return null;
}

 

算法2：

创建一个纵横长度分别是两个字符串长度的矩阵。初始化矩阵全0，然后遍历两个字符串，修改在相同字符所对应坐标的矩阵元素的值，使其等于左上角元素值加1。最后根据矩阵中最大值返回公串。

 

public String maxMutualStr2(String str1, String str2)
{
    int[][] matrix = new int[str1.length()][str2.length()];//Java在这里对0长度数组的处理很好

    int pos = -1;
    int len = 0;
    for (int i = 0; i < str1.length(); ++i)
    {
        for (int j = 0; j < str2.length(); ++j)
        {
            if (str1.charAt(i) == str2.charAt(j))
            {
                matrix[i][j] = (i > 0 && j > 0) ? (matrix[i - 1][j - 1] + 1) : 1;
                if (matrix[i][j] > len)
                {
                    len = matrix[i][j];
                    pos = i;
                }
            }
        }
    }

    return len > 0 ? str1.substring(pos - len + 1, pos + 1) : null;
}

 

显然，算法1的效率要比算法2差，因为有M*N次的字符串查找操作。算法2占用的空间有没有办法压缩压缩呢。。。