描述
对于给定的两个字符串 s 和 t，你需要找出它们的最长公共子串的长度。
子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
如果字符串 a 的一个子串 a′ 与字符串 b 的一个子串 b′ 完全相等，那么子串 a′,b′ 是字符串 a,b 的一个公共子串。
子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
如果字符串 a 的一个子串 a′ 与字符串 b 的一个子串 b′ 完全相等，那么子串 a′,b′ 是字符串 a,b 的一个公共子串。
输入描述：
第一行输入一个长度为 1≦len(s)≦150、仅由小写字母组成的字符串 s。
第二行输入一个长度为 1≦len(t)≦150、仅由小写字母组成的字符串 t。
输出描述：
输出一个整数，代表 s 和 t 的最长公共子串的长度。
解法一：（java）
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
// while (in.hasNextInt()) { // 注意 while 处理多个 case
// int a = in.nextInt();
// int b = in.nextInt();
// System.out.println(a + b);
// }
String str1 = in.nextLine();
String str2 = in.nextLine();
int len1 = str1.length();
int len2 = str2.length();
int max = 0;
for (int i = 0 ; i < len1 ; i++) {
for (int j = i ; j < len1 ; j++) {
String sub = str1.substring(i,j+1);
if (str2.contains(sub)) {
max = Math.max(max,sub.length());
}
}
}
System.out.println(max);
}
}思路：双层循环，对其中一个字符串进行切割，判断是否第二个字符串是否包含切割后的字符串，如果包含就和保存的最大长度做对比，取最大值。遍历结束返回打印最大值即可。
解法二（java）
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
// while (in.hasNextInt()) { // 注意 while 处理多个 case
// int a = in.nextInt();
// int b = in.nextInt();
// System.out.println(a + b);
// }
String str1 = in.nextLine();
String str2 = in.nextLine();
int len1 = str1.length();
int len2 = str2.length();
int max = 0;
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1 ; i <= len1 ; i++) {
for(int j = 1 ; j <= len2 ; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
max = Math.max(max,dp[i][j]);
}
}
}
System.out.println(max);
}
}思路：动态规划，动态规划表 dp 记录了以每个字符结尾的公共子串长度，通过状态转移逐步填充表格，最终找到最大值。