要求
给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。
输入描述
命令行工具接收两个字符串参数。输入字符串的合法字符集为[a-zA-Z0-9]，大小写敏感，无需考虑异常输入场景。输出描述
输出一行最长公共子串
示例
输入
1ABCD2345G 12345EF
输出
2345
解法一：滑动窗口法
滑动窗口法可以看成两列火车，一列静止一列逐步向前行驶。
将字符串长度较短的strA看作上面的静止列车，字符串较长的strB看作下面滑动的列车，strB经过strA一共分为三个阶段：
①B的火车头进入A，一直往右边移动 但火车头没有离开A
②B火车头跑出出了A，火车尾还没有进入A
③B火车尾进入A，继续往前开，但是火车尾还没有离开A
public String findCommonSubStr(String strA, String strB) {
//一定要先明确strA和strB哪个长哪个短
return strA.length() < strB.length() ? findMax(A, strB) : findMax(strB, A);
}
//strA串的长度较小， strB串的长度较大
String findMax(String strA, String strB) {
String result = "";
String maxStr = "";
//B的火车头进入A，一直往右边移动 但火车头没有离开A
for (int len = 1; len <= strA.length(); len++) {
maxStr = maxStr(strA, 0, strB, strB.length() - len, len);
if (maxStr.length() > result.length()) {
result = maxStr;
}
}
// B火车头跑出了A，火车尾还没有进入A
for (int j = strB.length() - strA.length(); j >= 0; j--) {
maxStr = maxStr(strA, 0, strB, j, strA.length());
if (maxStr.length() > result.length()) {
result = maxStr;
}
}
//B火车尾进入A，继续往前开，但是火车尾还没有离开A
for (int i = 1; i < strA.length(); i++) {
maxStr = maxStr(strA, i, B, 0, strA.length() - i);
if (maxStr.length() > result.length()) {
result = maxStr;
}
}
return result;
}
//strA子串从i位置和strB子串的j位置对齐，然后开始从头一一比对各个字符是否相同
// len参数是指比对的最大长度
String maxStr(String strA, int i, String strB, int j, int len) {
int count = 0, max = 0;
int pos = 0;
for (int k = 0; k < len; k++) {
if (strA.charAt(i + k) == strB.charAt(j + k)) {
count++;
} else if (count > 0) {
if (count > max) {
max = count;
pos = j + k;
}
count = 0;
}
}
//在上面的for循环中，当k=len-1时,count可能也++了，所以下面的代码还要做个特殊判断
if (count > 0 && count > max) {
max = count;
pos = j + len;
}
return strB.substring(pos - max, pos);
}解法二：动态规划
dp[i][j]表示nums1[i...end]与nums2[j...end]的最长公共前缀部分的长度
如果 nums1[i] == nums2[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1
如果 nums1[i] != nums2[j]，那么前缀部分肯定是不相同的，所以 dp[i][j] = 0
在这个过程中记录下dp数组的最大值即可，即 res
因为dp[i][j]是从dp[i + 1][j + 1]转移而来的，所以要倒着遍历数组
public String findCommonSubStr(String str1, String str2) {
int str1lenth = str1.length(), str2lenth = str2.length();
int[][] dp = new int[str1lenth + 1][str2lenth + 1];
int maxLength = 0; //公共子串的最大长度
int pos = -1;//因为我们的最长公共子串是从s2中截取的，所以这里用pos来标识s2中公共子串的结束位置索引
for (int i = str1lenth - 1; i >= 0; i--) {
for (int j = str2lenth - 1; j >= 0; j--) {
dp[i][j] = str1.charAt(i) == str2.charAt(j) ? dp[i + 1][j + 1] + 1 : 0;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
pos = j;
}
}
}
return str2.substring(pos, pos + maxLength);
}解法三：二维数组划“捺”法
将两个数组看成二维数组的样式，从右上角点开始，划“捺”，定义出发点，出发点一开始时（0，m-1），出发点向左移动，一直移动到左上角以后，开始从左上角往左下角向下移动
import java.io.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
String s1 = read.readLine();
String s2 = read.readLine();
int n = s2.length();
int m = s1.length();
int col = m-1;//出发点的列
int row = 0;//出发点的行
int max=0;//最大长度
int pos = -1;//因为我们的最长公共子串是从s2中截取的，所以这里用pos来标识s2中公共子串的结束位置索引
while(col!=0 || row < n){
//初始化 i,j
int i = row;
int j = col;
int len = 0;
while(i<n && j<m){//划“捺”，这里的while()里面的限制就是为了不让划“捺”划到超出整个棋盘
if(s1.charAt(j) == s2.charAt(i)){
len++;
if(len>max){
max = len;
pos = i;
}
}else{
len=0;
}
i++;
j++;
}
if(col == 0){//如果出发点已经移到了最左边了，那就只能向下方移动了
row++;
}else{ //如果没有移到最左边，那就继续往左边移动
col--;
}
}
String str = s2.substring(pos-max+1,pos+1);
if(str.length()==0){
str = "-1";
}
System.out.println(str);
}
}