题解 | #查找两个字符串a,b中的最长公共子串#

import sys

string_a = input()
string_b = input()


def find_max_string_length(str_1, str_2):
    if len(str_1) > len(str_2):  # str_1 永远是最短的
        str_1, str_2 = str_2, str_1

    n = len(str_1)
    max_word = (0, "")  # length, word
    for x in range(1, n + 1):  # 遍历可能的字符串长度
        for l_index in range(n):  # 左指针遍历
            r_index = x + l_index - 1
            if r_index > n:
                break
            new_str = str_1[l_index : r_index + 1]
            if (l := len(new_str)) > max_word[0] and new_str in str_2:
                max_word = (l, new_str)
    return max_word[1]


def find_max_string_length_2(str_1, str_2):
    if len(str_1) > len(str_2):  # str_1 永远是最短的
        str_1, str_2 = str_2, str_1

    m,n = len(str_2), len(str_1)
    max_word = (0, "")  # length, word
    dp = [[0]*m for _ in range(n)]
    for le in range(n):  # 遍历短串str_1
        for la in range(m):  # 遍历长串str_2
            if str_1[le] == str_2[la]:
                if le == 0 or la == 0:
                    dp[le][la]=1
                else:
                    dp[le][la]=1 + dp[le-1][la-1]
            if dp[le][la] > max_word[0]:
                max_word = (dp[le][la], str_1[le-dp[le][la]+1:le+1])
    return max_word[1]


print(find_max_string_length_2(string_a, string_b))

暴力搜索 和 动态规划