【最长公共子串】空间优化的动态规划

• 问题分解
  • 求最长公共子串长度
  • 记录最长公共子串的位置
  • 截取最长公共子串
• 动态规划
  • 状态定义：为以为结尾和以为结尾的最长公共子串的长度
  • 状态方程：当第个字符等于第个字符时，；不相等时，
  • 状态初始化：和元素为0，由于默认初始值为0，无需操作
• 空间优化
  • 考虑到仅与有关，所以可以把二维状态压缩为一维
  • 每轮从后往前更新，计算第轮的时，用到的属于第轮的更新值

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[] dp = new int[len2 + 1];
        int maxLenSub = 0;
        int end = 0;
        for (int i = 1; i <= len1; i ++) {
            for(int j = len2; j >= 1; j --) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {     
                    dp[j] = dp[j-1] + 1;
                    int t = maxLenSub;
                    maxLenSub = Math.max(maxLenSub, dp[j]);
                    if (maxLenSub > t) {
                        end = i;
                    }
                } else {
                    dp[j] = 0;
                }
            }
        }
        return str1.substring(end - maxLenSub, end);
    }
}