什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！我们只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！时间复杂度：O(n)
题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:return 0
left = 0
lookup = set()
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:max_len = cur_len
lookup.add(s[i])
return max_len或者使用字典dict:
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
from collections import defaultdict
lookup = defaultdict(int)
start = 0
end = 0
max_len = 0
counter = 0
while end < len(s):
if lookup[s[end]] > 0:
counter += 1
lookup[s[end]] += 1
end += 1
while counter > 0:
if lookup[s[start]] > 1:#例如 abdhb
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len, end - start)
return max_len
最长公共连续子串(Longest Common Substring)
给定字符串str = “ABCDADNENXY”
子序列：从str中任意去掉若干个(含0个)字符，剩下的就是这个str的子序列，如ABC, ABXY, DADXY等，中间不必连续.
子串：和子序列不同，子串必须是连续的，如ABCD，ENXY，CDADNE都是子串，而AXY不是，因为中间断开了，把连续.
子串必定是子序列，子序列不一定是子串.
问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。
比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。
算法思路：
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。
针对于上面的两个字符串我们可以得到的二维矩阵如下：
从上图可以看到，str1和str2共有5个公共子串，但最长的公共子串长度为5。
为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由record[i][j]=1演变为record[i][j]=1 +record[i-1][j-1]，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：
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 #最长匹配的长度
p=0 #最长匹配对应在s1中的最后一位
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
if m[i+1][j+1]>mmax:
mmax=m[i+1][j+1]
p=i+1
return s1[p-mmax:p],mmax #返回最长子串及其长度
print find_lcsubstr('abcdfg','abdfg') C++：
string getLCS(string str1, string str2) {
vector<vector<int> > record(str1.length(), vector<int>(str2.length()));
int maxLen = 0, maxEnd = 0;
for(int i=0; i<static_cast<int>(str1.length()); ++i)
for (int j = 0; j < static_cast<int>(str2.length()); ++j) {
if (str1[i] == str2[j]) {
if (i == 0 || j == 0) {
record[i][j] = 1;
}
else {
record[i][j] = record[i - 1][j - 1] + 1;
}
}
else {
record[i][j] = 0;
}
if (record[i][j] > maxLen) {
maxLen = record[i][j];
maxEnd = i; //若记录i,则最后获取LCS时是取str1的子串
}
}
return str1.substr(maxEnd - maxLen + 1, maxLen);
}
from：
https://blog.csdn.net/qq_25800311/article/details/81607168
from：
https://blog.csdn.net/baobao3456810/article/details/79770367