实用价值
比如，用于比较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);
}
}
