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

问题：有两个字符串 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…