Loading…
Loading…
The same table as LCS with one rule flipped: a mismatch resets the cell to 0, because a substring has to be contiguous.
The border row and column are 0: an empty prefix shares no substring with anything.
1int longestCommonSubstring(String a, String b) {2 int m = a.length(), n = b.length(), best = 0;3 int[][] dp = new int[m + 1][n + 1];4 for (int i = 1; i <= m; i++)5 for (int j = 1; j <= n; j++)6 if (a.charAt(i-1) == b.charAt(j-1)) {7 dp[i][j] = dp[i-1][j-1] + 1;8 best = Math.max(best, dp[i][j]);9 } else dp[i][j] = 0; // reset — a substring cannot skip a character10 return best;11}