How can I find the length of the longest common substring between two strings efficiently?

I have two strings, s1 and s2, and I need to find the length of the longest substring that appears in both strings. The substring must be contiguous in both s1 and s2.

For example:

• If s1 = "abcde" and s2 = "cdefg", the longest common substring is "cde", which has a length of 3.

• If s1 = "abcdef" and s2 = "ghijkl", there is no common substring, so the result should be 0.

I'm looking for an efficient solution that can handle large strings, up to 1000 characters long.

I tried using a brute force method by checking all substrings of one string and seeing if they exist in the other string. However, this approach is too slow for large input sizes. I was expecting an efficient solution using dynamic programming, but I'm not sure how to set it up correctly.

Here's what I've tried so far:

def longestCommonSubstring(s1, s2): dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] max_len = 0 for i in range(1, len(s1) + 1): for j in range(1, len(s2) + 1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 max_len = max(max_len, dp[i][j]) return max_len 

This works fine for smaller test cases, but I'm wondering if it's the most efficient solution or if there are better approaches. Is there a way to improve it, or is this a reasonable approach for large inputs?