BinarySearch 0193 Longest Common Substring

Problem statement

https://binarysearch.com/problems/Longest-Common-Substring/

Solution

Equal to Leetcode 0718. Maximum Length of Repeated Subarray.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, A, B):
        n, m = len(A), len(B)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n):
            for j in range(m):
                if A[i] == B[j]:
                    dp[i][j] = dp[i-1][j-1]+1
        return max(max(row) for row in dp)