求2个字符串的最长公共子串

实用价值

比如，用于比较2个DNA序列中最大相同的部分。

思路1

遍历两个数组，碰到相同的字符就继续比较它们接下来的字符，只要相同就继续比较下去，直到字符不同或者字符串末尾，然后查看它是不是最长的公共子串。这样遍历完就可以得到两个字符串的公共子串了。不过这个算法太慢了，已经达到了3次方的级别了，是O(m×n×m)了。

思路2

使用动态规划算法，画表格解决问题。该问题的极限子问题就是1个字符的比较了，每个单元格的左上角单元格就是2个数组中每个字符前面的那个字符是否相等。于是只要2字符串的字符不相等那对应的单元格就置0，否则就等于1+它左上角的单元格中的值。于是就可以得到想要的结果了，这个的时间复杂度是O(m×n)，时间也不短啊。

代码使用

package com.company;

public class Main {

    public static void main(String[] args) {
    // write your code here
        String string0 = "abcdefghijklmnop";
        String string1 = "abcsafjklmnopqrstuvw";
        System.out.println(Solution.findLongestCommonSubstring0(string0,string1));
    }
}

输出

jklmnop

Process finished with exit code 0

代码实现

package com.company;

public class Solution {
    /**
     * 找出两个字符串的最长公共子串
     * 本方法采用的是遍历的方式，时间复杂度是O(n^3)。
     * 时间有点长啊！
     * @param string0
     * @param string1
     * @return
     */
    static public String findLongestCommonSubstring(String string0,String string1) {
        StringBuilder maxSubstring = new StringBuilder();
        for (int counter = 0;counter < string0.length();counter++) {
            for (int counter0 = 0;counter0 < string1.length();counter0++) {
                int pointer0 = counter;
                int pointer1 = counter0;
                int commonSubstringLength = 0;
                while (pointer0 < string0.length()
                        && pointer1 < string1.length()
                        && string0.charAt(pointer0) == string1.charAt(pointer1)) {
                    commonSubstringLength++;
                    if (commonSubstringLength > maxSubstring.length()) {
                        maxSubstring.delete(0,maxSubstring.length());
                        maxSubstring.append(string0.substring(counter,pointer0 + 1));
                    }
                    pointer0++;
                    pointer1++;
                }
            }
        }
        return maxSubstring.toString();
    }

    /**
     * 所谓动态规划思想就是认为大问题可以被拆分成小问题。
     * 它一般有3个性质:
     * 1、无论是总问题还是子问题都存在最优解。
     * 2、某问题只取决于它的子问题，和由它组成的问题没关系。
     * 3、各子问题之间大多是相互关联的。
     * 它每一阶段都有各个子问题的最优解，各子问题的最优解
     * 会产生往往会重复计算，于是用一个表把它们存储起来。
     * 具体到本问题就是每一个字符的相同，然后逐步到原来
     * 问题的解。
     * 本问题的解是两个字符串的最长公共子串，那么它的子
     * 问题的解的极限是1个字符是否相同。
     * 在解集中每个单元格的左上角的单元格就是前面相邻的两
     * 个字符是否相同。并且如果该单元格对应的下标不同，那
     * 么单元格可以立刻被置0.否则它就应该加上左上角的单元
     * 格中的解的值。
     * 应用动态规划算法以后时间复杂度变成了O(n^2)。
     * @param string0
     * @param string1
     * @return
     */
    static public String findLongestCommonSubstring0(String string0,String string1) {
        int[][] answerArray = new int[string0.length()][string1.length()];
        int maxSubstringLength = 0;
        int startLongestIndex = 0;
        for (int counter = 0;counter < string0.length();counter++) {
            for (int counter0 = 0;counter0 < string1.length();counter0++) {
                if (string0.charAt(counter) == string1.charAt(counter0)) {
                    if (counter - 1 >= 0 && counter0 - 1 >= 0)answerArray[counter][counter0] = answerArray[counter - 1][counter0 - 1] + 1;
                    else answerArray[counter][counter0] = 1;
                    if (answerArray[counter][counter0] > maxSubstringLength) {
                        maxSubstringLength = answerArray[counter][counter0];
                        startLongestIndex = counter - maxSubstringLength + 1;
                    }
                } else answerArray[counter][counter0] = 0;
            }
        }
        return string0.substring(startLongestIndex,startLongestIndex + maxSubstringLength);
    }
}