【动态规划】最长公共子串问题

2021-03-11 约 1100 字预计阅读 3 分钟 - 次阅读

题目来源为：牛客网

题目有意思的地方在于，最长公共子串与最长连续公共子串都是比较经典的问题，但是这道题在其基础上加了限制。首先这道题应该是最长连续公共子串问题，状态转移方程就不写了，挺简单的。就记录下最大的子串所在的位置的行坐标和列坐标，就能把子串拿到手。但是对于O(nm)的动态规划所有点都会超时，这就很厉害了，目前通过的做法使用的是滑动窗口法，我还在研究。

代码大概长这样

/**
 * 滑动窗口算法
 *
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
public static String LCS1(String str1, String str2) {
    // write code here
    StringBuilder sb = new StringBuilder();
    int start = 0, end = 1;
    while (end < str1.length() + 1) {
        if (str2.contains(str1.substring(start, end))) {
            if (sb.length() < end - start) {
                sb.delete(0, sb.length());
                sb.append(str1, start, end);
            }
        } else {
            //这个算法我曾经疑惑，假如出现start>end，程序不是会crash么
            //通过debug发现，当start==end时，substring获取的是""，此时contains必然为true
            //所以当start == end时，必然会走end++分支
            start++;
        }
        end++;
    }
    if (sb.length() == 0) {
        return "-1";
    }
    return sb.toString();
}

我的理解是start和end维护了一个滑动窗口。（java的substring是前闭后开，所以开始只有一个字母）

如果滑动窗口存在，则长度增加
如果不存在，则起始位置增加
每次遇到最长的时候都记录下来。

我一开始比较疑惑的地方在于，这样做为什么能够保证正确性，就没太想明白。后面我想通了，正着想比较困难，我是反着想的。就假设str1串和str2串之间存在着一个长度为maxlen的最大子串，开始位置在maxbeg。一个很显然的情况是，该子串一定是通过滑动窗口的方式过去的。就有两种情况，一种是滑动窗口在匹配到最大子串前长度不够，显然它能够顺利增长到匹配为止。另一种情况是滑动窗口的起始点没有匹配到子串的起始点，它显然也会不断失配往后移动。因此，该滑动窗口一定能匹配到最大连续公共子串。

C++题解，不过只有93%的击败率。应该是一些细节吧，比如使用数组会比vector要快一些等。但大致思路已经是差不多的

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution{
public:
    bool check(string S,string P){
        //检查S子串中是否存在P子串
        //根据P子串构建next数组
        vector<int> nxt(P.length(),0);
        size_t point = 1;
        size_t now = 0;
        while(point<P.length()){
            //第一种情况，now==point
            if(P[point] == P[now]){
                point++;
                now++;
            }
            else if(now>0){
                now = nxt[now-1];
            }
            else{
                point++;
            }
        }
        //开始匹配
        unsigned int tar = 0; //S
        unsigned int pos = 0; //P
        while(tar<S.length()){
            if(S[tar] == P[pos]){
                tar++,pos++;
            }else if(pos>0){
                pos = nxt[pos-1];
            }else{
                tar++;
            }

            if(pos==P.length()){
                return true;
            }
        }
        return false;
    }


    string LCS(string str1,string str2){
        int maxStart = -1,maxLen = -1;
        size_t start = 0;
        size_t len = 1;
        size_t size1 = str1.length();
        while(start + len <= size1){
            //长度没有超
            //子串 str1.substr(start,len) 是否存在于str2中 ! 如何快速判断，
            // 如果存在，则记录，并累加
            if(this->check(str2,str1.substr(start,len))){
                cout<<start<<" "<<len<<endl;
                cout<<str1.substr(start,len)<<endl;
                maxStart = start;
                maxLen = len;
                len++;
            }
            // 如果不存在，滑动窗口继续滑动
            else{
                start++;
            }
        }
        if(maxStart == -1){
            return "-1";
        }else{
            return str1.substr(maxStart,maxLen);
        }
    }

};

int main(void){
    Solution s;
    string str1("22222"),str2("22222");
    //cin>>str1>>str2;
    cout<<s.LCS(str1,str2)<<endl;
    cout<<s.check(str1,str2)<<endl;
}