最长公共子串

[编程题]最长公共子串

热度指数：4016 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有两个字符串（可能包含空格）,请找出其中最长的公共连续子串,输出其长度。

输入描述:

给定两行字符串

长度在1000以内

输出描述:

输出这两个字符串的最长公共连续子串的长度

示例1

输入

abcde
bcd

输出

算法知识视频讲解

Python

华科平凡

Python解法

LCS问题就是求两个字符串最长公共子串的问题。

解法:

用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0。
求出对角线最长的1的序列，其对应的位置就是最长匹配子串的位置。

def find_lcsubstr(s1, s2):
    m = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]  # 生成0矩阵，为方便后续计算，比字符串长度多了一列
    mmax = 0  # 最长匹配的长度
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                m[i + 1][j + 1] = m[i][j] + 1
                mmax = max(mmax, m[i + 1][j + 1])
    return mmax  # 返回最长长度
print(find_lcsubstr(input(), input()))

编辑于 2019-02-24 11:54:12 回复(1)