最长公共子序列LCS 和最长公众子串

51Nod-1006-最长公共子序列LCS
最长公众子串

51Nod-1006-最长公共子序列LCS

题目链接

http://www.51nod.com/Challenge/Problem.html#!#problemId=1006

题目

就是输入两个字符串str1、str2，输出任意一个最长公共子序列。

解析

dp[i][j]代表的是 : 必须以str1[i]、str2[j]结尾的最长公共子序列，dp[i][j]来源:

可能是dp[i-1][j]，代表str1[0~i-1]与str2[0~j]的最长公共子序列。
可能是dp[i][j-1]，代表str1[0~i]与str2[0~j-1]的最长公共子序列。
如果str1[i] == str2[j]，还可能是dp[i-1][j-1] + 1。

这三种情况中取最大值。

在这里插入图片描述

构造结果的过程(利用dp数组即可)

从矩阵的右下角开始，有三种移动方式: 向上、向左、向左上。
如果dp[i][j] > dp[i-1][j] && dp[i][j] > dp[i][j-1]，说明之前在计算dp[i][j]的时候，一定是选择了dp[i-1][j-1]+1，所以可以确定str1[i] = str2[j]，并且这个字符一定输入最长公共子序列，把这个字符放进结果字符串，然后向左上方移动；
如果dp[i][j] == dp[i-1][j]，说明之前计算dp[i][j]的时候，dp[i-1][j-1]+1不是必须的选择，向上方移动即可；
如果dp[i][j] == dp[i][j-1]，向左方移动即可；
如果dp[i][j]同时等于dp[i-1][j]和dp[i][j-1]，向上向左都可以，选择一个即可，不会错过必须选择的字符；

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 ``` import java.io.BufferedInputStream; import java.util.Scanner; public class Main { /** dp[i][j]代表的是 str[0..i]与str[0…j]的最长公共子序列*/ public static int[][] getDp(char[] sa,char[] sb){ int[][] dp = new int[sa.length][sb.length]; dp[0][0] = sa[0] == sb[0] ? 1 : 0; for(int i = 1; i < sa.length; i++) // 一旦dp[i][0]被设置成1,则dp[i~N-1][0]都为1 dp[i][0] = Math.max(dp[i-1][0], sa[i] == sb[0] ? 1 : 0); for(int j = 1; j < sb.length; j++) dp[0][j] = Math.max(dp[0][j-1], sb[j] == sa[0] ? 1 : 0); for(int i = 1; i < sa.length; i++){ for(int j = 1; j < sb.length; j++){ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); if(sa[i] == sb[j]){ dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + 1); } } } return dp; } /*** 求出最长公共子序列*/ public static String getLCS(String sa, String sb, int[][] dp){ if(sa == null


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59`	``` import java.io.BufferedInputStream; import java.util.Scanner; public class Main { /** dp[i][j]代表的是 str[0..i]与str[0…j]的最长公共子序列/ public static int[][] getDp(char[] sa,char[] sb){ int[][] dp = new int[sa.length][sb.length]; dp[0][0] = sa[0] == sb[0] ? 1 : 0; for(int i = 1; i < sa.length; i++) // 一旦dp[i][0]被设置成1,则dp[i~N-1][0]都为1 dp[i][0] = Math.max(dp[i-1][0], sa[i] == sb[0] ? 1 : 0); for(int j = 1; j < sb.length; j++) dp[0][j] = Math.max(dp[0][j-1], sb[j] == sa[0] ? 1 : 0); for(int i = 1; i < sa.length; i++){ for(int j = 1; j < sb.length; j++){ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); if(sa[i] == sb[j]){ dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + 1); } } } return dp; } /** 求出最长公共子序列*/ public static String getLCS(String sa, String sb, int[][] dp){ if(sa == null

最长公众子串

题目链接

https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602?toCommentId=1532408

解析

dp矩阵第一列即dp[0~N-1][0]，对某一个位置(i,0)来说，如果str1[i] == str2[0]，令dp[i][0] = 1，否则令dp[i][0] = 0；
矩阵dp第一行，即dp[0][0~M-1]，对某个位置(0,j)来说，如果str1[0] == str2[j]，令dp[0][j] = 1，否则令dp[0][j] = 0；
一般的位置有两种情况，如果str1[i] != str2[j]，说明在必须把str1[i]和str2[j]当做公共子串最后一个字符是不可能的，所以dp[i][j] = 0；如果str1[i] = str2[j]，说明可以将str1[i]和str2[j]作为公共子串的最后一个字符，其长度就是dp[i-1][j-1] + 1；

在这里插入图片描述

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*; public class LongestSubstring { public int findLongest(String A, int n, String B, int m) { char[] sa = A.toCharArray(); char[] sb = B.toCharArray(); int[][] dp = new int[sa.length][sb.length]; for(int i = 0; i < sa.length; i++) //注意和最长公共子序列有点不同 dp[i][0] = sa[i] == sb[0] ? 1 : 0; for(int j = 0; j < sb.length; j++) dp[0][j] = sa[0] == sb[j] ? 1 : 0; int res = 0; for(int i = 1; i < sa.length; i++){ for(int j = 1; j < sb.length; j++){ if(sa[i] == sb[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; res = Math.max(res, dp[i][j]); } } } return res; //dp数组中的最大值，就是最大公共字串的长度 } }


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23`	import java.util.*; public class LongestSubstring { public int findLongest(String A, int n, String B, int m) { char[] sa = A.toCharArray(); char[] sb = B.toCharArray(); int[][] dp = new int[sa.length][sb.length]; for(int i = 0; i < sa.length; i++) //注意和最长公共子序列有点不同 dp[i][0] = sa[i] == sb[0] ? 1 : 0; for(int j = 0; j < sb.length; j++) dp[0][j] = sa[0] == sb[j] ? 1 : 0; int res = 0; for(int i = 1; i < sa.length; i++){ for(int j = 1; j < sb.length; j++){ if(sa[i] == sb[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; res = Math.max(res, dp[i][j]); } } } return res; //dp数组中的最大值，就是最大公共字串的长度 } }

由dp表生成答案字符串也是不难的，找到最大值，然后往左边的res个字符就是答案。

测试程序:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ``` public class LCSub { public static int[][] getDp(char[] sa,char[] sb){ int[][] dp = new int[sa.length][sb.length]; for(int i = 0; i < sa.length; i++) //注意和最长公共子序列有点不同 dp[i][0] = sa[i] == sb[0] ? 1 : 0; for(int j = 0; j < sb.length; j++) dp[0][j] = sa[0] == sb[j] ? 1 : 0; int res = 0; for(int i = 1; i < sa.length; i++){ for(int j = 1; j < sb.length; j++){ if(sa[i] == sb[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; res = Math.max(res, dp[i][j]); } } } System.out.println(res); //4 return dp; //dp数组中的最大值，就是最大公共字串的长度 } /** 根据dp表得到答案*/ public static String getLongestSubstring(String sa, String sb, int[][] dp){ if(sa == null


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46`	``` public class LCSub { public static int[][] getDp(char[] sa,char[] sb){ int[][] dp = new int[sa.length][sb.length]; for(int i = 0; i < sa.length; i++) //注意和最长公共子序列有点不同 dp[i][0] = sa[i] == sb[0] ? 1 : 0; for(int j = 0; j < sb.length; j++) dp[0][j] = sa[0] == sb[j] ? 1 : 0; int res = 0; for(int i = 1; i < sa.length; i++){ for(int j = 1; j < sb.length; j++){ if(sa[i] == sb[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; res = Math.max(res, dp[i][j]); } } } System.out.println(res); //4 return dp; //dp数组中的最大值，就是最大公共字串的长度 } /** 根据dp表得到答案*/ public static String getLongestSubstring(String sa, String sb, int[][] dp){ if(sa == null

另外，还有一种可以优化空间的做法:

因为dp[i][j]只依赖于左上角位置的dp[i-1][j-1]，所以用一个变量记录左上角的值即可。
遍历方向从右上角的斜线开始，一直遍历到左下角，中间记录最大值max和结束位置end即可。

代码如下:


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30`	``` public static String getLongestSubstring2(String sa,String sb){ if(sa == null