本文共 2896 字，大约阅读时间需要 9 分钟。

知识点：

最长公共子串问题是寻找两个或多个已知字符串最长的子串。

此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。

例如：

str1="123ABCD4567"      str2 = "ABE12345D6"

最长公共子串是：123

最长公共子序列是：123456

1.最长公共子串

题目描述：

 计算两个字符串的最大公共字串的长度，字符不区分大小写。

 输入描述：输入两个字符串，分两行输入。

 输出描述：输出一个整数。

 示例：

 输入：

 asdfas

输出：6

思路：

dp[i][j] -- 表示以str1[i]和str2[j]为结尾的最长公共子串

当str1[i] == str2[j]时，dp[i][j] = dp[i-1][j-1] + 1;

否则，dp[i][j] = 0;

最优解为max(dp[i][j]),其中0<=i<len1, 0<=j<len2;

实现：

import java.util.Scanner;public class LongestCommonSubString {	 public static void main(String[] args) {	        Scanner sc = new Scanner(System.in);	        while (sc.hasNextLine()) {	            String str1 = sc.nextLine().toLowerCase();	            String str2 = sc.nextLine().toLowerCase();	            System.out.println(getCommonStrLength(str1, str2));	        }	    }	 	    private static int getCommonStrLength(String str1, String str2) {	        int len1 = str1.length();	        int len2 = str2.length();	        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;	                } else {	                    dp[i][j] = 0;	                }	            }	        }	        int max = 0;	        for (int i = 0; i <= len1; i++) {	            for (int j = 0; j <= len2; j++) {	                if (dp[i][j] > max) {	                    max = dp[i][j];	                }	            }	        }	        return max;	    }}

2.最长公共子序列

LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。

比如，对于char x[]="aabcd";有顺序且相互相邻的aabc是其子序列，有顺序但是不相邻的abc也是其公共子序列。即，只要得出序列中各个元素属于所给出的数列，就是子序列。再加上char y[]="12abcabcd";对比出才可以得出最长公共子序列abcd。

题目描述：

计算两个字符串的最长公共子序列的长度，字符不区分大小写。

 输入描述：输入两个字符串，分两行输入。

 输出描述：输出一个整数。

示例：

 输入：

ABCBDAB

思路：

公式推导参见

dp[i][j] 表示子串A[0...i]（数组长度为n）和子串B[0...j]（数组长度为m）的最长公共子序列

当A[i] == B[j]时，dp[i][j] = dp[i-1][j-1] + 1;

否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

最优解为dp[n-1][m-1];

实现：

import java.util.Scanner;public class LongestCommonSubSeq {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        while (sc.hasNextLine()) {            String str1 = sc.nextLine().toLowerCase();            String str2 = sc.nextLine().toLowerCase();            System.out.println(findLCS(str1, str1.length(), str2, str2.length()));        }    }    public static int findLCS(String A, int n, String B, int m) {        int[][] dp = new int[n + 1][m + 1];        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= m; j++) {                if (A.charAt(i - 1) == B.charAt(j - 1)) {                    dp[i][j] = dp[i - 1][j - 1] + 1;                } else {                	dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);                }            }        }        return dp[n][m];    }}

参考：

根据该博客写的代码并做了总计和修改。

转载地址：http://jmdgj.baihongyu.com/