Longest Common Substring using Dynamic Programming

This problem can be solved using dynamic programming in O(len(X) * len(Y)), see this. In this article we are going to discuss about an efficient approach.

Given two strings X and Y, the task is to find the length of the longest common substring. 

Examples:

Input: X = “w3wiki”, y = “GeeksQuiz” 
Output: 5 
Explanation: The longest common substring is “Geeks” and is of length 5.

Input: X = “abcdxyz”, y = “xyzabcd” 
Output: 4 
Explanation: The longest common substring is “abcd” and is of length 4.

Input: X = “zxabcdezy”, y = “yzabcdezx” 
Output: 6 
Explanation: The longest common substring is “abcdez” and is of length 6.