最长公共子字符串算法 JAVA实现

什么是最长公共子字符串算法? 举一个例子就清楚了
比如我们有两个字符串:
Please, peter go swimming!
I’m peter goliswi
那么该算法应该输出’peter go’. 最长公共子字符串算法通过suffix trees算法 (时间复杂度O(n),但是实现极其复杂) 可以获得效率很高的实现。但是在本帖中我们要使用效率稍次的‘动态编程’思想来实现该算法。动态编程，顾名思义， 就是重用前一步已经计算出来的信息。要理解这种实现，我们首先需要填写一个二维的整数型数组，假如我们用i表示水平方向的字符串（Please, peter go swimming!），以j表示垂直方向的字符串(I’m peter goliswi) 如图：

please, peter go swimming
i 0000000000000000000100100
' 0000000000000000000000000
m 0000000000000000000011000
  0000000100000100100000000
p 1000000020000000000000000
e 0010010003000000000000000
t 0000000000400000000000000
e 0010010001050000000000000
r 0000000000006000000000000
  0000000100000700100000000
g 0000000000000080000000000
o 0000000000000009000000000
l 0100000000000000000000000
i 0000000000000000000100100
s 0001000000000000010000000
w 0000000000000000002000000
i 0000000000000000000300100

当i=19 j=0时我们得到第一个相等的字符‘i’,这时把相应的index对应的数组值设为1；
依此类推继续填表;
当 i= 8  j= 4时我们得到另一个相等的字符’ ’（空格），现在我们要重用前一步的计算结果(num[7][3]=1)
所以num[8][4] = 1 + num[7][3]就应该是2.这样我们就得到了一个长度为2的相等子字符串；
以此规则填完这个动态表;

下面是一段参考实现

public static String longestSubstring(String str1, String str2) {

StringBuilder sb = new StringBuilder();
if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())
  return "";

// ignore case
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

// java initializes them already with 0
int[][] num = new int[str1.length()][str2.length()];
int maxlen = 0;
int lastSubsBegin = 0;

for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
  if (str1.charAt(i) == str2.charAt(j)) {
    if ((i == 0) || (j == 0))
       num[i][j] = 1;
    else
       num[i][j] = 1 + num[i - 1][j - 1];

    if (num[i][j] > maxlen) {
      maxlen = num[i][j];
      // generate substring from str1 => i
      int thisSubsBegin = i - num[i][j] + 1;
      if (lastSubsBegin == thisSubsBegin) {
         //if the current LCS is the same as the last time this block ran
         sb.append(str1.charAt(i));
      } else {
         //this block resets the string builder if a different LCS is found
         lastSubsBegin = thisSubsBegin;
         sb = new StringBuilder();
         sb.append(str1.substring(lastSubsBegin, i + 1));
      }
   }
}
}}

return sb.toString();
}