Longest Common Substring
Posted: 14 Mar, 2021
You have been given two strings 'STR1' and 'STR2'. You have to find the length of the longest common substring.
A string “s1” is a substring of another string “s2” if “s2” contains the same characters as in “s1”, in the same order and in continuous fashion also.
For example :
If 'STR1' = “abcjklp” and 'STR2' = “acjkp” then the output will be 3. Explanation: The longest common substring is “cjk” which is of length 3.
The first line contains an integer ‘T’ which denotes the number of test cases. The first and only line of each test case contains two space-separated strings 'STR1' and 'STR2', respectively.
For each test case, return the length of the longest common substring among the two strings. Print the output of each test case in a separate line.
You don't need to print anything, it has been already taken care of. Just implement the given function.
1 <= T <= 100 1 <= |STR1|, |STR2| <= 100 Where |STR1| and |STR2| are the lengths of the string 'STR1' and 'STR2' respectively. Time limit: 1 sec
The basic idea is to recursively try and match characters from ‘STR1’ to characters of ‘STR2’ and vice versa also.
The steps are as follows:
- Create a ‘COUNT’ variable initialized to 0 to get the length of the longest common substring.
- Try to match the last characters of both strings. Let ‘i’ be the last index for ‘STR1’ and ‘j’ be the last index of ‘STR2’, so match ‘STR1’[i] and ‘STR2’[j].
- If they match, increment ‘COUNT’ by 1 and try to match the preceding characters.
- If they do not match, make a recursive call to compare ‘STR1’[i -1] with ‘STR2’[j] and compare ‘STR1’[i] with ‘STR2’[j -1] and we should choose the option which maximises our answer i.e. return max(“previous ‘COUNT’”, ‘COUNT’ obtained by matching ‘STR1’[i-1] with ‘STR2’[j] and ‘COUNT’ obtained by matching ‘STR1’[i-1] with ‘STR2’[j]).
- Keep repeating these steps until we reach the starting of the two strings.
Longest Common Prefix
Posted: 24 Jul, 2021
Posted: 28 Jul, 2021
Posted: 29 Jul, 2021
Posted: 31 Jul, 2021
Posted: 21 Aug, 2021