题目来源为：牛客网
题目有意思的地方在于，最长公共子串与最长连续公共子串都是比较经典的问题，但是这道题在其基础上加了限制。 首先这道题应该是最长连续公共子串问题，状态转移方程就不写了，挺简单的。就记录下最大的子串所在的位置的行坐标和列坐标，就能把子串拿到手。 但是对于O(nm)的动态规划所有点都会超时，这就很厉害了，目前通过的做法使用的是滑动窗口法，我还在研究。
代码大概长这样
代码语言：javascript复制/**
* 滑动窗口算法
*
* @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要快一些等。但大致思路已经是差不多的
代码语言：javascript复制#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;
}
