Find the Longest Common Substring Between Two Code Snippets with DP

Problem Statement

Given two strings text1 and text2 (each length between 1 and 100, consisting of letters, digits and spaces), output any longest continuous substring that appears in both strings. If no common substring exists, output an empty string.

Input: two lines – the first line contains text1, the second line contains text2.

Output: a single line containing one longest common substring.

Examples

Example 1

hello123world
hello123abc4

Output: hello123 Example 2

private_void_method
public_void_method

Output: _void_method Example 3

hiworld
hiweb

Output:

hiw

Solution Idea

This is the classic Longest Common Substring problem solved with dynamic programming. Create a 2‑dimensional DP table dp of size (m+1) × (n+1), where m = len(text1) and n = len(text2). The entry dp[i][j] stores the length of the longest common suffix of the prefixes text1[:i] and text2[:j].

Recurrence:

if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = 0

During the fill, maintain maxLength – the largest value seen – and the corresponding substring ans = text1[i-maxLength:i]. Initialise the first row and column with zeros because an empty prefix cannot share a non‑empty substring.

Reference Implementation (Python)

# Problem: Find the longest common substring between two strings
text1 = input()
text2 = input()

m = len(text1)
n = len(text2)

# dp[i][j] = length of longest common suffix of text1[:i] and text2[:j]
# Initialise a (m+1) x (n+1) matrix filled with 0
dp = [[0] * (n + 1) for _ in range(m + 1)]

maxLength = 0
ans = ""

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if text1[i - 1] == text2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            if dp[i][j] > maxLength:
                maxLength = dp[i][j]
                ans = text1[i - maxLength:i]
        else:
            dp[i][j] = 0

print(ans)

Complexity Analysis

Time complexity: O(m × n) – each cell of the DP matrix is processed once.

Space complexity: O(m × n) – the full 2‑D DP table is stored.