### Question

Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

For example, if the given strings are “GeeksforGeeks” and “GeeksQuiz”, the output should be 5 as longest common substring is “Geeks”.

### Solution

This question is to be distinguished from **[LintCode] Longest Common Subsequence**.

The solution is DP, too. Even the code is similar. Read my code below.

**Updated on Jan 26th, 2015**: there is another approach using **Suffix Array**, suggested by this post - but wait! Do not try to read that article, because you won’t easily understand its explanations. I will summarize it in simple English:

- Concatenate String X with a “#” sign, and String Y with a “$” sign.
- Build a suffix tree using both strings
- find out node with
**both “$” and “#” as child**.

In the case of (X = xabxa, and Y = babxba), the branch “abx” would be the deepest node that qualifies. Thus the result. Code is not written.

### Code

```
public String LCSubstr(String s, String t) {
int longest = 0;
int tPos = -1;
// dp[i][j] represents the LCSubstr ending at position i and j
int[][] dp = new int[t.length() + 1][s.length() + 1];
for (int i = 1; i <= t.length(); i++) {
for (int j = 1; j <= s.length(); j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > longest) {
longest = dp[i][j];
tPos = i;
}
}
}
}
return t.substring(tPos - longest, tPos);
}
```