Problem Statement

Given two strings. The task is to find the length of the longest common substring.

Example 1:

Input:S1 = "ABCDGH", S2 = "ACDGHR"
Output: 4
Explanation: The longest common substring
is "CDGH" which has length 4.

Example 2:

Input: S1 = "ABC", S2 "ACB"
Output: 1
Explanation: The longest common substrings
are "A", "B", "C" all having length 1.

Problem Link

Longest Common Substring | Practice | GeeksforGeeks

Code

int longestCommonSubstr (string S1, string S2, int n, int m)
    {
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        int res = 0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(S1[i-1]==S2[j-1])
                dp[i][j] = 1+dp[i-1][j-1];
                
                else
                dp[i][j] = 0;
                
                res = max(res,dp[i][j]);
            }
        }
        return res;
    }

Complexity Analysis

Time and Space Complexity of the above implementation is O(mn)