# Longest Common Substring
## Problem Statement
\
Given two strings. The task is to find the length of the longest common substring.
\
**Example 1:**
Input: S1 = "ABCDGH", S2 = "ACDGHR", n = 6, m = 6
Output: 4
Explanation: The longest common substring
is "CDGH" which has length 4.
**Example 2:**
Input: S1 = "ABC", S2 "ACB", n = 3, m = 3
Output: 1
Explanation: The longest common substrings
are "A", "B", "C" all having length 1.
\
**Your Task:**\
You don't need to read input or print anything. Your task is to complete the function **longestCommonSubstr()** which takes the string S1, string S2 and their length n and m as inputs and returns the length of the longest common substring in S1 and S2.
\
**Expected Time Complexity:** O(n\*m).\
**Expected Auxiliary Space:** O(n\*m).
\
**Constraints:**\
1<=n, m<=1000
## Intuition
```
Approach:
We cannot memoize this, as this will boil down to LCS problem, Because if no
match we will have to return and cannot match earlier elements
So, We check for every character matching using bootom up and update the count
```
### Links
### Video Links
### Approach 1:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
int longestCommonSubstr (string s1, string s2, int n, int m){
int maxi=0;
vector>dp(n+1,vector(m+1,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]=dp[i-1][j-1]+1;
maxi=max(maxi,dp[i][j]);
}
}
}
return maxi;
}
```
{% endcode %}
### Approach 2:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 3:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 4:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Similar Problems
###
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-strings/longest-common-substring.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.