DP #17. Longest Common Substring - mbhushan/dynpro GitHub Wiki

####(17). Longest Common Substring.

Given two strings, find longest common substring between them.

String X = abcdaf
String Y = zbcdf
Longest common substring: 3 (bcd)

Formula:
if (Y[i] == X[j]) {
    T[i][j] = T[i-1][j-1] + 1;
} else {
    T[i][j] = 0;
}

	0	a	b	c	d	a	f
0	0	0	0	0	0	0	0
z	0	0	0	0	0	0	0
b	0	0	1	0	0	0	0
c	0	0	0	2	0	0	0
d	0	0	0	0	3	0	0
f	0	0	0	0	0	0	1

Longest Common Substring

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)