最长公共子序列
这个这个最长公共子序列是非连续的，比如1234和42354的最长公共子序列为234
最优子结构性质：
设序列 X=<x1, x2, …, xm> 和 Y=<y1, y2, …, yn> 的一个最长公共子序列 Z=<z1, z2, …, zk>，则：
若 xm ≠ yn， 要么Z是 Xm-1 和 Y 的最长公共子序列，要么 Z 是X和 Yn-1 的最长公共子序列。
2.1 若 xm ≠ yn 且 zk≠xm ，则 Z是 Xm-1 和 Y 的最长公共子序列；
2.2 若 xm ≠ yn 且 zk ≠yn ，则 Z 是X和 Yn-1 的最长公共子序列。
综合一下2 就是求二者的大者
计算最优值：
子问题空间中，总共只有O(m*n) 个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
长度表C 和 方向变量B：
与最长递增子序列相比，最长公共子序列有以下不同点：
针对的是两个序列，求它们的最长公共子序列。
在最长递增子序列中，dp[i] 表示以 Si 为结尾的最长递增子序列长度，子序列必须包含 Si ；在最长公共子序列中，dp[i][j] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含 S1i 和 S2j 。
在求最终解时，最长公共子序列中 dp[N][M] 就是最终解，而最长递增子序列中 dp[N] 不是最终解，因为以 SN 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。
/* 动态规划
* 求最长公共子序列
* @ author by gsm
* @ 2015.4.1
*/
import java.util.Random;
public class LCS {
public static int[][] lengthofLCS(char[] X, char[] Y){
/* 构造二维数组c[][]记录X[i]和Y[j]的LCS长度 (i,j)是前缀
* c[i][j]=0; 当 i = j = 0;
* c[i][j]=c[i-1][j-1]+1; 当 i = j > 0; Xi == Y[i]
* c[i][j]=max(c[i-1][j],c[i][j+1]); 当 i = j > 0; Xi != Y[i]
* 需要计算 m*n 个子问题的长度 即 任意c[i][j]的长度
* -- 填表过程
*/
int[][]c = new int[X.length+1][Y.length+1];
// 动态规划计算所有子问题
for(int i=1;i<=X.length;i++){
for (int j=1;j<=Y.length;j++){
if(X[i-1]==Y[j-1]){
c[i][j] = c[i-1][j-1]+1;
}
else if(c[i-1][j] >= c[i][j-1]){
c[i][j] = c[i-1][j];
}
else{
c[i][j] = c[i][j-1];
}
}
}
// 打印C数组
for(int i=0;i<=X.length;i++){
for (int j=0;j<=Y.length;j++){
System.out.print(c[i][j]+" ");
}
System.out.println();
}
return c;
}
// 输出LCS序列
public static void print(int[][] arr, char[] X, char[] Y, int i, int j) {
if(i == 0 || j == 0)
return;
if(X[i-1] == Y[j-1]) {
System.out.print("element " + X[i-1] + " ");
// 寻找的
print(arr, X, Y, i-1, j-1);
}else if(arr[i-1][j] >= arr[i][j-1]) {
print(arr, X, Y, i-1, j);
}else{
print(arr, X, Y, i, j-1);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
char[] x ={'A','B','C','B','D','A','B'};
char[] y ={'B','D','C','A','B','A'};
int[][] c = lengthofLCS(x,y);
print(c, x, y, x.length, y.length);
}
}
精简版
public int lengthOfLCS(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (nums1[i - 1] == nums2[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[n1][n2];
}
最长公共子串
一个问题
定义 2 个字符串 query 和 text, 如果 query 里最大连续字符子串在 text 中存在，则返回子串长度. 例如: query=”acbac”，text=”acaccbabb”， 则最大连续子串为 “cba”, 则返回长度 3.
方法
时间复杂度：O(m*n)的DP 这个 LCS 跟前面说的最长公共子序列的 LCS 不一样，不过也算是 LCS 的一个变体，在 LCS 中，子序列是不必要求连续的，而子串则是 “连续” 的
我们还是像之前一样 “从后向前” 考虑是否能分解这个问题，类似最长公共子序列的分析，这里，我们使用c[i,j] 表示 以 Xi 和 Yj 结尾的最长公共子串的长度，因为要求子串连续，所以对于 Xi 与 Yj 来讲，它们要么与之前的公共子串构成新的公共子串；要么就是不构成公共子串。故状态转移方程
X[i-1] == Y[j-1]，c[i,j] = c[i-1,j-1] + 1；
X[i-1] != Y[j-1]，c[i,j] = 0；
对于初始化，i==0 或者 j==0，c[i,j] = 0
public class LCString {
public static int lengthofLCString(String X, String Y){
/* 构造二维数组c[][]记录X[i]和Y[j]的LCS长度 (i,j)是前缀
* c[i][j]=0; 当 i = j = 0;
* c[i][j]=c[i-1][j-1]+1; 当 i = j > 0; Xi == Y[i]
* c[i][j]=0; 当 i = j > 0; Xi != Y[i]
* 需要计算 m*n 个子问题的长度 即 任意c[i][j]的长度
* -- 填表过程
*/
int[][]c = new int[X.length()+1][Y.length()+1];
int maxlen = 0;
int maxindex = 0;
for(int i =1;i<=X.length();i++){
for(int j=1;j<=Y.length();j++){
if(X.charAt(i-1) == Y.charAt(j-1)){
c[i][j] = c[i-1][j-1]+1;
if(c[i][j] > maxlen)
{
maxlen = c[i][j];
maxindex = i + 1 - maxlen;
}
}
}
}
return maxlen;
}
public static void main(String[] args) {
String X = "acbac";
String Y = "acaccbabb";
System.out.println(lengthofLCString(X,Y));
}
}
最长前缀LCP Longest common prefix
求两个字符串任意两个位置开头的最长公共前缀。时间复杂度o(n2) 如果是暴力需要o(n3) 枚举i,j然后到头。
class Strings:
def LongestCommonPrefix(a, b):
# lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
n, m = len(a), len(b)
lcp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
if a[i] == b[j]:
lcp[i][j] = lcp[i + 1][j + 1] + 1
return lcp