Find the longest common substring of two given strings.

Assumptions

• The two given strings are not null

Examples

• S = “abcde”, T = “cdf”, the longest common substring of S and T is “cd”

Solution: match[i][j]: s前i个字母和t前j个字母的longest common substring (including i and j)

s.charAt(i - 1) == t.charAt(j - 1)时，match[i][j] = match[i - 1][j - 1] + 1，否则match[i][j] = 0 (注意与subsequence的区别)

用start和longest记录开始位置和最长长度

  public String longestCommon(String s, String t) {
    int[][] match = new int[s.length() + 1][t.length() + 1];
    int start = 0, longest = 0;
    for (int i = 1; i <= s.length(); i++) {
      for (int j = 1; j <= t.length(); j++) {
        if (s.charAt(i - 1) == t.charAt(j - 1)) {
          match[i][j] = match[i - 1][j - 1] + 1;
          if (match[i][j] > longest) {
            longest = match[i][j];
            start = i - longest;
          }
        } else {
          match[i][j] = 0;
        }
      }
    }
    return s.substring(start, start + longest);
  }