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

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def longestCommonSubstr(self, S1, S2, n, m):

        # code here

Solutions:
class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		length = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					length = max(length, dp[i][j])
				else:
					dp[i][j] = 0
		return length


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		import sys
		ans = -1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = 0
				ans = max(dp[i][j], ans)
		return ans

	def solve(self, n, m, s1, s2, dp):
		if n < 0 or m < 0:
			return 0
		if dp[n][m] != -1:
			return dp[n][m]
		if s1[n] == s2[m]:
			x = 1 + self.solve(n - 1, m - 1, s1, s2, dp)
		else:
			x = max(max(self.solve(n - 1, m, s1, s2, dp), self.solve(n, m - 1, s1, s2, dp)), x)
		dp[n][m] = x
		return x


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[0 for a in range(n + 1)] for b in range(m + 1)]
		res = 0
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif S2[i - 1] == S1[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					res = max(res, dp[i][j])
				else:
					dp[i][j] = 0
		return res


class Solution:

	def longestCommonSubstr(self, X, Y, m, n):
		dp = [[0 for k in range(n)] for l in range(m)]
		result = 0
		for i in range(m):
			for j in range(n):
				if X[i] == Y[j]:
					dp[i][j] = (dp[i - 1][j - 1] if i > 0 and j > 0 else 0) + 1
				else:
					dp[i][j] = 0
				result = max(result, dp[i][j])
		return result


class Solution:

	def longestCommonSubstr(self, X, Y, m, n):
		LCSuff = [[0 for k in range(n + 1)] for l in range(m + 1)]
		result = 0
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					LCSuff[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1
					result = max(result, LCSuff[i][j])
				else:
					LCSuff[i][j] = 0
		return result


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		ans = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if S2[i - 1] == S1[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					ans = max(ans, dp[i][j])
		return ans

	def helper(self, S1, S2, n, m, dp):
		if n == 0 or m == 0:
			return 0
		if S1[n - 1] == S2[m - 1]:
			self.ans = max(1 + self.helper(S1, S2, n - 1, m - 1, dp), self.ans)
		l = self.helper(S1, S2, n - 1, m, dp)
		r = self.helper(S1, S2, n, m - 1, dp)
		return 0


class Solution:

	def longestCommonSubstr(self, text1, text2, n, m):
		ans = 0
		Max = 0
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if text1[i - 1] == text2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					Max = max(Max, dp[i][j])
				else:
					dp[i][j] = 0
		return Max


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		d = [[0 for h in range(m + 1)] for g in range(n + 1)]
		mx = 0
		for h in range(1, n + 1):
			for g in range(1, m + 1):
				if S1[h - 1] == S2[g - 1]:
					d[h][g] = 1 + d[h - 1][g - 1]
					mx = max(d[h][g], mx)
				else:
					d[h][g] = 0
		return mx


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = []
		res = 0
		for i in range(n + 1):
			dp.append([0] * (m + 1))
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					res = max(res, dp[i][j])
		return res


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		table = [[0 for x in range(m + 1)] for y in range(n + 1)]
		max = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					table[i][j] = table[i - 1][j - 1] + 1
					if table[i][j] > max:
						max = table[i][j]
		return max


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		dp = [0 for i in range(m + 1)]
		ma = 0
		for i in range(1, n + 1):
			for j in range(m, 0, -1):
				if s1[i - 1] == s2[j - 1]:
					dp[j] = 1 + dp[j - 1]
					ma = max(dp[j], ma)
				else:
					dp[j] = 0
		return ma


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		ma = 0
		arr = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] != S2[j - 1]:
					arr[i][j] = 0
				else:
					arr[i][j] = 1 + arr[i - 1][j - 1]
					if arr[i][j] > ma:
						ma = arr[i][j]
		return ma


import numpy as np

class Solution:

	def dp_sol(self, S1, S2, n, m):
		dp = np.array([[0] * (m + 1)] * (n + 1))
		maxa = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					maxa = max(dp[i][j], maxa)
		return maxa

	def longestCommonSubstr(self, S1, S2, n, m):
		return self.dp_sol(S1, S2, n, m)


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[0] * m for _ in range(n)]
		res = 0
		for i in range(n):
			for j in range(m):
				if S1[i] != S2[j]:
					dp[i][j] = 0
					continue
				if i == 0 or j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i - 1][j - 1] + 1
				res = max(res, dp[i][j])
		return res


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		l = []
		for i in range(len(S1)):
			for j in range(i + 1, len(S1) + 1):
				k = S1[i:j]
				if k in S2:
					l.append(k)
				else:
					break
		if len(l) == 0:
			return 0
		l.sort(key=len)
		return len(l[-1])


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		table = [[0] * (m + 1) for i in range(n + 1)]
		maxlen = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					table[i][j] = table[i - 1][j - 1] + 1
					if table[i][j] > maxlen:
						maxlen = table[i][j]
				else:
					table[i][j] = 0
		return maxlen


class Solution:

	def longestCommonSubstr(self, S1, S2, m, n):
		dp = [[0 for x in range(n + 1)] for y in range(m + 1)]
		max_len = 0
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					max_len = max(max_len, dp[i][j])
				else:
					dp[i][j] = 0
		return max_len


class Solution:

	def longestCommonSubstr(self, str1, str2, n, m):
		m = len(str1)
		n = len(str2)
		matrix = [[0] * (n + 1) for _ in range(m + 1)]
		max_length = 0
		end_position = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if str1[i - 1] == str2[j - 1]:
					matrix[i][j] = matrix[i - 1][j - 1] + 1
					if matrix[i][j] > max_length:
						max_length = matrix[i][j]
						end_position = i
		longest_substring = str1[end_position - max_length:end_position]
		return len(longest_substring)


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		t = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(m + 1):
			t[0][i] = 0
		for j in range(n + 1):
			t[j][0] = 0
		maxx = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
					maxx = max(maxx, t[i][j])
				else:
					t[i][j] = 0
		return maxx


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		stateMap = [[0 for i in range(m + 1)] for _ in range(n + 1)]
		maxVal = 0
		for r in range(1, n + 1):
			for c in range(1, m + 1):
				if S1[r - 1] == S2[c - 1]:
					stateMap[r][c] = stateMap[r - 1][c - 1] + 1
					maxVal = max(maxVal, stateMap[r][c])
		return maxVal


class Solution:

	def longestCommonSubstr(self, s1, s2, n1, n2):

		def lcs(i1, i2, n1, n2, s1, s2, dp):
			ans = 0
			for i1 in range(n1):
				for i2 in range(n2):
					if s1[i1] == s2[i2]:
						if i1 > 0 and i2 > 0:
							dp[i1][i2] = dp[i1 - 1][i2 - 1] + 1
						else:
							dp[i1][i2] = 1
						ans = max(ans, dp[i1][i2])
					else:
						dp[i1][i2] = 0
			return ans
		dp = []
		for i in range(n1):
			dp.append([-1] * n2)
		return lcs(0, 0, n1, n2, s1, s2, dp)


import sys

class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		t = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = 0
		mx = -sys.maxsize
		for i in range(n + 1):
			for j in range(m + 1):
				mx = max(mx, t[i][j])
		return mx


class Solution:

	def longestCommonSubstr(self, str1, str2, n, m):
		dp = []
		p = []
		result = 0
		for i in range(n + 1):
			for j in range(m + 1):
				p.append(0)
			dp.append(p)
			p = []
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif str1[i - 1] == str2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					result = max(result, dp[i][j])
				else:
					dp[i][j] = 0
		return result


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp_array = [[0 for i in range(m + 1)] for i in range(n + 1)]
		for i in range(m):
			dp_array[0][i] = 0
		for j in range(n):
			dp_array[j][0] = 0
		maxl = 0
		for ind1 in range(1, n + 1):
			for ind2 in range(1, m + 1):
				if S1[ind1 - 1] == S2[ind2 - 1]:
					dp_array[ind1][ind2] = 1 + dp_array[ind1 - 1][ind2 - 1]
					maxl = max(maxl, dp_array[ind1][ind2])
				else:
					dp_array[ind1][ind2] = 0
		return maxl


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		_res = [[0 for k in range(m + 1)] for l in range(n + 1)]
		_max = 0
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					_res[i][j] = 0
				elif S1[i - 1] == S2[j - 1]:
					_res[i][j] = _res[i - 1][j - 1] + 1
					_max = max(_max, _res[i][j])
				else:
					_res[i][j] = 0
		return _max


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		prev = [0] * (m + 1)
		curr = [0] * (m + 1)
		maxm = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					curr[j] = 1 + prev[j - 1]
					maxm = max(maxm, curr[j])
				else:
					curr[j] = 0
			prev = curr[:]
		return maxm


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[None] * (m + 1) for _ in range(n + 1)]
		for i in range(m + 1):
			dp[0][i] = 0
		for i in range(n + 1):
			dp[i][0] = 0
		maxm = float('-inf')
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					maxm = max(maxm, dp[i][j])
				else:
					dp[i][j] = 0
		if maxm == float('-inf'):
			return 0
		return maxm


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[0] * m for _ in range(n)]
		max1 = 0
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0:
					if S1[i] == S2[j]:
						dp[i][j] = 1
						max1 = max(dp[i][j], max1)
				elif S1[i] == S2[j]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					max1 = max(max1, dp[i][j])
		return max1


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for ind1 in range(n + 1):
			dp[ind1][0] = 0
		for ind2 in range(m + 1):
			dp[0][ind2] = 0
		ans = 0
		for ind1 in range(1, n + 1):
			for ind2 in range(1, m + 1):
				if S1[ind1 - 1] == S2[ind2 - 1]:
					dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
					ans = max(ans, dp[ind1][ind2])
				else:
					dp[ind1][ind2] = 0
		return ans


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		res = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0:
					res[i][j] = 0
				if j == 0:
					res[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					res[i][j] = 1 + res[i - 1][j - 1]
				else:
					res[i][j] = 0
		ans = -99
		for i in range(n + 1):
			ans = max(max(res[i]), ans)
		return ans


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		l = [[0] * (m + 1) for t in range(n + 1)]
		res = 0
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					l[i][j] = 0
				elif S1[i - 1] == S2[j - 1]:
					l[i][j] = 1 + l[i - 1][j - 1]
					res = max(res, l[i][j])
				else:
					l[i][j] = 0
		return res


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		maxCommonLength = 0
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				if dp[i][j] > maxCommonLength:
					maxCommonLength = dp[i][j]
		return maxCommonLength


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):

		def lcs(t1, t2):
			m = len(t1)
			n = len(t2)
			dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
			ml = 0
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					if t1[i - 1] == t2[j - 1]:
						dp[i][j] = 1 + dp[i - 1][j - 1]
						if dp[i][j] > ml:
							ml = dp[i][j]
					else:
						dp[i][j] = 0
			return ml
		return lcs(S1, S2)


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		res = [[0 for a in range(n + 1)] for b in range(m + 1)]
		for i in range(m):
			for j in range(n):
				if s1[j] == s2[i]:
					res[i + 1][j + 1] = 1 + res[i][j]
		max1 = 0
		for i in res:
			max1 = max(max1, max(i))
		return max1


class Solution:

	def longestCommonSubstr(self, s1, s2, x, y):
		x = len(s1)
		y = len(s2)
		maxi = 0
		dp = [[-1 for j in range(y + 1)] for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
					continue
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					maxi = max(maxi, dp[i][j])
				else:
					dp[i][j] = 0
		return maxi


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		res = 0
		matrix = []
		for i in range(n + 1):
			matrix.append([0] * (m + 1))
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					matrix[i][j] = matrix[i - 1][j - 1] + 1
					res = max(matrix[i][j], res)
		return res


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		dp = [[0 for k in range(m + 1)] for l in range(n + 1)]
		result = 0
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					result = max(result, dp[i][j])
				else:
					dp[i][j] = 0
		return result


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		if m == 0 or n == 0:
			return 0
		if m > n:
			return self.longestCommonSubstr(S2, S1, m, n)
		longest = 0
		count = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
		for row in range(1, m + 1):
			for col in range(1, n + 1):
				if S2[row - 1] == S1[col - 1]:
					count[row][col] = count[row - 1][col - 1] + 1
					longest = max(longest, count[row][col])
		return longest


class Solution:

	def __init__(self):
		self.count = 0
		self.maxi = 0

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[-1] * (m + 1) for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for j in range(m + 1):
			dp[0][j] = 0
		maxi = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					maxi = max(maxi, dp[i][j])
				else:
					dp[i][j] = 0
		return maxi


class Solution:

	def longestCommonSubstr(self, str1, str2, m, n):
		matrix = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				matrix[i][j] = 0
		longest_substring = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if str1[i - 1] == str2[j - 1]:
					matrix[i][j] = matrix[i - 1][j - 1] + 1
					if matrix[i][j] > longest_substring:
						longest_substring = matrix[i][j]
				else:
					matrix[i][j] = 0
		return longest_substring


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		ans = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					ans = max(ans, dp[i][j])
		return ans


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		table = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		memo = [0]
		for i in range(n):
			for j in range(m):
				if S1[i] == S2[j]:
					table[i + 1][j + 1] = 1 + table[i][j]
					memo.append(table[i + 1][j + 1])
		return max(memo)


class Solution:

	def longestCommonSubstr(self, s1, s2, x, y):
		dp = [[0] * (y + 1) for i in range(x + 1)]
		max = 0
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > max:
						max = dp[i][j]
				else:
					dp[i][j] = 0
		return max


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		c = 0
		mx = 0
		i = 0
		j = 0
		while j < n:
			t = s1[i:j + 1]
			if t in s2:
				c += 1
				j += 1
			else:
				if c > mx:
					mx = c
				i += 1
				j = i
				c = 0
		if c > mx:
			mx = c
		return mx


class Solution:

	def longestCommonSubstr(self, s1, s2, n, m):
		maxx = 0
		dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
		for ind1 in range(1, len(s1) + 1):
			for ind2 in range(1, len(s2) + 1):
				if s1[ind1 - 1] == s2[ind2 - 1]:
					dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
					maxx = max(dp[ind1][ind2], maxx)
		return maxx


class Solution:
	dp = []

	def gen(self, s, t, n, m, c):
		if m == 0 or n == 0:
			return c
		if s[n - 1] == t[m - 1]:
			c = self.gen(s, t, n - 1, m - 1, c + 1)
		l = self.gen(s, t, n - 1, m, 0)
		r = self.gen(s, t, n, m - 1, 0)
		return max(l, r, c)

	def longestCommonSubstr(self, s, t, n, m):
		dp = []
		for i in range(n + 1):
			b = []
			for j in range(m + 1):
				b.append(-1)
			dp.append(b)
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(m + 1):
			dp[0][i] = 0
		maxi = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					if dp[i][j] > maxi:
						maxi = dp[i][j]
				else:
					dp[i][j] = 0
		return maxi


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		ans = 0
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					ans = max(ans, dp[i][j])
		return ans

	def dfs(self, S1, S2, n, m, dp):
		if n == 0 or m == 0:
			return 0
		elif dp[n][m] != -1:
			return dp[n][m]
		if S1[n - 1] == S2[m - 1]:
			dp[n][m] = 1 + self.dfs(S1, S2, n - 1, m - 1, dp)
		else:
			return 0
		return dp[n][m]


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		max_val = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					max_val = max([max_val, dp[i][j]])
		return max_val


class Solution:

	def longestCommonSubstr(self, S1, S2, n, m):
		(string1, string2) = (S1, S2)
		prev_dp = [1 if string1[0] == char else 0 for char in string2]
		ans = max(prev_dp)
		for i in range(1, n):
			current_dp = [0] * m
			current_dp[0] = 1 if string1[i] == string2[0] else 0
			ans = max(ans, current_dp[0])
			for j in range(1, m):
				current_dp[j] = 0 if string1[i] != string2[j] else 1 + prev_dp[j - 1]
				ans = max(ans, current_dp[j])
			prev_dp = current_dp
		return ans


class Solution:

	def longestCommonSubstr(self, text1, text2, n, m):
		ma = 0
		dp = [0 for i in range(len(text2) + 1)]
		cur = [0 for i in range(len(text2) + 1)]
		for i in range(1, len(text1) + 1):
			for j in range(1, len(text2) + 1):
				if text1[i - 1] == text2[j - 1]:
					cur[j] = 1 + dp[j - 1]
					ma = max(ma, cur[j])
				else:
					cur[j] = 0
			dp = cur[:]
		return ma