[Question] Longest Common Substring

Question

link

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:

1. Concatenate String X with a “#” sign, and String Y with a “$” sign.
2. Build a suffix tree using both strings
3. 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);
}