题解 | #最长公共子序列(二)#二维动态规划#上交机试

https://www.acwing.com/problem/content/3511/

本题主要思路与上题类似，头文件只用到了一部分我懒得调所以都粘上来了

修改的地方：由于需要连续的公共子序列，且只要小写字母不要数字，故相比（一）做出如下改动

1.if语句条件改为判断此时是否为小写字母&&两字符串元素是否相等

2.满足if语句则仍将该节点值置为上一节点的值加一，同时判断该节点值是否超过由整型变量currentmax记录的最大值，若超过则更新currentmax

2.若不满足if语句则将该节点值置为0（为了保证连续子串的性质）

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <cstring>

using namespace std;
short dp[10002][10002];
int minpubstr(char* arr1,char* arr2){
    int n=strlen(arr1);
    int m=strlen(arr2);
    int curretmax=0;
    for(int i=1;i<=n;i++) dp[i][0]=0;
    for(int j=1;j<=m;j++) dp[0][j]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(arr1[i-1]>='a'&&arr1[i-1]<='z'&&arr1[i-1]==arr2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
                curretmax= max(curretmax,(int)dp[i][j]);
            }
            else{
                dp[i][j]=0;
            }
        }
    }
    return curretmax;
}
int main(){
    char arr1[10002];
    char arr2[10002];
    scanf("%s",arr1);
    scanf("%s",arr2);
    printf("%d", minpubstr(arr1,arr2));
    return 0;
}