page contents
首页 问答
正文

如何求两个字符串的最长公共子串？

轩辕小不懂 发布于 2022-03-29 15:54
阅读 614
收藏 0
答案 1
分类：人工智能
  • 人工智能
  • python
  • 编程论坛

    • 找出两个字符串的最长公共子串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。

    默认排序 时间排序
    3394
    Nen
    Nen
    - 程序员

    滑动比较法

    这种方法的主要思路为：保持s1的位置不变，然后移动s2，接着比较它们重叠的字符串的公共子串（记录最大的公共子串的长度maxLen以及最长公共子串在s1中结束的位置maxLenEnd1），在移动的过程中，如果当前重叠子串的长度大于maxLen，那么更新maxLen为当前重叠子串的长度。最后通过maxLen和maxLenEnd1就可以找出它们最长的公共子串。实现方法如图9-19所示。

    attachments-2022-03-HXF41y5o6242c5caa5e51.png

    图9-19 滑动窗口方法

    在图9-19中，这两个字符串的最长公共子串为“bc”，实现代码如下：

    attachments-2022-03-GrRHKvoF6242c5eb7ca50.png、attachments-2022-03-j58U7Qby6242c5fb7516e.png

    算法性能分析：这种方法用双重循环来实现，外层循环的次数为m+n(其中，m和n分别为两个字符串的长度)，内层循环最多执行n次，算法的时间复杂度为O((m+n)×n)。此外，这种方法只使用了几个临时变量，因此算法的空间复杂度为O(1)。

    请先 登录 后评论
    轩辕小不懂
    1 关注
     
    轩辕小不懂
    提出于 2022-03-29 15:54
    全部

    轩辕小不懂 的其他提问

    类似问题

    运行时异常与一般异常有何异同？
    1 回答
    614 阅读
    String 和StringBuffer的区别？
    2 回答
    614 阅读
    怎样将字符串中第一个字母大写？
    3 回答
    614 阅读
    在Python中如何生成一个随机数？
    1 回答
    614 阅读
    Python中的不可变集合（frozenset）是什么？
    1 回答
    614 阅读
    在Python中怎样获取输入？
    1 回答
    614 阅读