关于动态规划:算法最长公共子串

问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。

比方：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。

计划：
如果字符雷同则置为1，否则置为0

缩小反复计算，arr[i] [j] = arr[i-1] [j-1]，此处要留神的点是当i==0 || j==0时要间接设值。

Java代码实现：

 // 动静布局实现，工夫复杂度O(m*n),空间复杂度(m*n)  private static String getLcs(String s1, String s2) {    int maxLen = 0, maxEnd = 0;    int[][] arr = new int[s1.length()][s2.length()];    for (int i = 0; i < s1.length(); i++) {      for (int j = 0; j < s2.length(); j++) {        if (s1.charAt(i) == s2.charAt(j)) {          if (i == 0 || j == 0) {            arr[i][j] = 1;          } else {            arr[i][j] = arr[i - 1][j - 1] + 1;          }        } else {          arr[i][j] = 0;        }        if (arr[i][j] > maxLen) {          maxEnd = i;          maxLen = arr[i][j];        }      }    }    if (maxLen == 0) {      return "";    }    return s1.substring(maxEnd - maxLen + 1, maxEnd);  }

参考文章 求两个字符串的最长公共子串https://blog.csdn.net/qq_2580...