跟子序列的方法很像，但是只需要dp[i][j]=dp[i-1][j-1]+1;，因为子串必须连续，所以不需要else的内容。
#include <bits/stdc++.h>
using namespace std;
#define N 1000
int dp[N][N]={0};
char a[N];
char b[N];
int main(){
int i,j;
int max_length=0;
scanf("%s %s",&a,&b);
int len_a=strlen(a);
int len_b=strlen(b);
int end_a=0;
int end_b=0;
for(i=1;i<len_a;i++){
for(j=1;j<len_b;j++){
if(a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
if(max_length<dp[i][j]){
max_length=dp[i][j];
end_a=i-1;
end_b=j-1;
}
}
}
}
cout<<"max:"<<max_length<<endl;
cout<<"end:"<<end_a<<" "<<end_b<<endl;
}
- 优化方法：
总有一次滑动能使得两个相同的子串可以对齐的。
窗口匹配.gif
固定一个，另外一个动。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
res=0
def run(pos1,pos2):
len1=len(nums1)
len2=len(nums2)
maxsize=0
while(pos1<len1 and pos2<len2):
if nums1[pos1]==nums2[pos2]:
start=pos1
while(pos1<len1 and pos2<len2 and nums1[pos1]==nums2[pos2]):
pos1+=1
pos2+=1
maxsize=max(maxsize,pos1-start)
else:
pos1+=1
pos2+=1
return maxsize
for i in range(0,len(nums1)):
res=max(res,run(i,0))
for i in range(0,len(nums2)):
res=max(res,run(0,i))
return res
