Introduction to Longest Common Substring
Let's get introduced to the Longest Common Substring pattern.
We'll cover the following...
Overview
In this pattern, we will be discussing 12 problems related to this pattern. The following diagram shows an overview of this pattern.
The Longest Common Substring (LCS) is defined as the longest substring that is common in the given two strings. In the longest common substring problems, the elements of a substring must be consecutive as in the original strings. A slight variation of LCS is the Longest Common Subsequence, in which the elements of the substrings are not necessarily required to occupy consecutive positions within the original strings. In either case, the indices of the common substring must be in strictly increasing order. A strictly increasing order means that the indices of the substring taken from the original string must be in ascending order.
A substring, X, is considered as the maximum common substring of strings, S1 and S2, if it exists in both S1 and S2 and no other common substring is greater in length than X.
If we take two strings, “BCDAACD” and “ACDBAC”, there could be many common subsequences of different lengths like “BC”, “CDAC”, “DAC”, “AAC”, “AC”, “CD” and so on, but the longest common subsequence is of length 4 which is “CDAC”.
Mathematically, it can be written as:
Given two strings and ...