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”

base line: m[0] [0]= 0

induction rule: m[i][j] indicates longest common substring between the first i + 1 letter from string1 and first j + 1 letter from string2

m[i][j] = m[i - 1][j - 1] + 1 if string1[i] == string2[j]

public class Solution {
  public String longestCommon(String s, String t) {
    // Write your solution here.
    if (s == null || t == null) {
      return null;
    }
    //char[] sc = s.toCharArray();
    //char[] tc = t.toCharArray();

    int longest = 0;
    int[][] common = new int[s.length()][t.length()];
    int start = 0;

    for(int i = 0; i < s.length(); i++) {
      for(int j = 0; j < t.length(); j++) {
        if (s.charAt(i) == t.charAt(j)) {
          if (i == 0 || j == 0) {
            common[i][j] = 1;
          } else {
            common[i][j] = common[i - 1][j - 1] + 1;
          }

          // update longest
          if(longest < common[i][j]) {
            longest = common[i][j];
            start = i - longest + 1;
          }
        }
      }
    }

    return s.substring(start,start + longest);
  }
}