最长公共子串

[编程题]最长公共子串

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

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

数据范围： $1 \le |str1|,|str2| \le 5000$
要求：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^2)$

示例1

输入

"1AB2345CD","12345EF"

输出

"2345"

备注:

算法知识视频讲解

推荐

bokerr

如图，自左上->右下的对折线上最长连续交点即为最大字串，为了节省内存开销我没使用二维数组，直接通过记录步长处理的，并在适当位置判断能否提前推出计算，最极限情况，0(2n) 即可退出(str2是str1子串)；反之则需要遍历，O(n*m)(最长字串只有一个字符)；

思路其实非常简单，代码看起来方法挺多只是我稍微封装了一下，为了看起来简洁；实际上这种程度的封装，在编译器优化时可以相当轻松的完成方法内联。(评论区贴的不一定是对的，我从评论区拷了很多个拿来测试都是过不了的，一度让我怀疑题目有bug，干了一些蠢事(羞耻到打滚))。

import java.util.*;
public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    //状态记录，取缔二维数组，减少内存开销
    int start = 0;
    int stepNum = 0;
    int currentStart = 0;
    int currentStepNum = 0;
    boolean cancleLeft = false;
    boolean cancleRight = false;
    int len2 = 0;
    public String LCS (String str1, String str2) {
        String breakJudge;
        if (str1.length() < str2.length()){
            String temp = str1; str1 = str2; str2 = temp;
        }
        len2 = str2.length();
        for (int i = 0;i < str1.length() && !cancleRight;i++){
            for (int j = 0; j < str2.length() && i + j < str1.length();j++)
                doJudge(str1,str2,j + i,j);
            clear();
            if (!cancleRight)
                cancleRight = breakJudge(str1.length(),i);
        }
        clear();
        for (int i = 0;i < str2.length() && ! cancleLeft;i++){
            for (int j = 0; i + j < str2.length();j++)
                doJudge(str1,str2,j,j + i);
            clear();
            if (!cancleLeft)
                cancleLeft = breakJudge(str2.length(),i);
        }
        return stepNum == 0 ? "-1" : str1.substring(start,start + stepNum);
    }
    // 判断能否提前退出
    public boolean breakJudge(int len,int i){
        if (stepNum == len2 || (stepNum >= (len - i))){
            return true;
        }
        return false;
    }

    public void clear(){
        if (currentStepNum > stepNum){
            stepNum = currentStepNum;
            start = currentStart;
        }
        currentStepNum = 0;
        currentStart = 0;
    }
    public void doJudge(String str1,String str2,int index1,int index2){
        if ( str1.charAt(index1) == str2.charAt(index2)){
            if (currentStepNum == 0)// 记录步长为0
                currentStart = index1; //更新起点
            currentStepNum ++;//步长加一
        } else
            clear();//不等，对比当前步长与缓存步长,更新保存的步长与起点
    }
}

编辑于 2021-07-06 10:32:40 回复(1)