最长公共子序列

公共子序列
f[i][j]表示a[0,...,i-1] 和 b[0,...,j-1] 最长公共子序列的长度。

import java.util.*;
public class Main {
    static int solution(char[] a, char[] b) {
        int n = a.length, m = b.length;
        int[][] f = new int[n+1][m+1];
        for(int i=1; i <= n; i++) {
            for(int j=1; j <= m; j++) {
                if(a[i-1] != b[j-1]) {
                    f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
                } else 
                    f[i][j] = f[i-1][j-1] + 1;
            }
        }
        //System.out.println(Arrays.deepToString(f));
        return f[n][m];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            char[] a = sc.next().toLowerCase().toCharArray();
            char[] b = sc.next().toLowerCase().toCharArray();
            int res = solution(a,b);
            System.out.println(res);
        }
    }
}

公共子串
f[i][j]表示以a[i-1] 和 b[j-1] 结尾的子串，最长公共子串的长度。

import java.util.*;
public class Main {
    static int solution(char[] a, char[] b) {
        int n = a.length, m = b.length;
        int[][] f = new int[n+1][m+1];
        for(int i=1; i <= n; i++) {
            for(int j=1; j <= m; j++) {
                if(a[i-1] == b[j-1])
                    f[i][j] = f[i-1][j-1] + 1;
            }
        }
        //System.out.println(Arrays.deepToString(f));
        int res = 0;
        for(int i=0; i <= n; i++)
            for(int j=0; j <= m; j++)
                res = Math.max(res, f[i][j]);
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            char[] a = sc.next().toLowerCase().toCharArray();
            char[] b = sc.next().toLowerCase().toCharArray();
            int res = solution(a,b);
            System.out.println(res);
        }
    }
}

最长公共子序列

原文：https://www.cnblogs.com/lixyuan/p/13257238.html