动态规划---最大公共子序列（连续）-蒲公英云

动态规划---最大公共子序列（连续）

矫情吗；* 2023-06-25 02:23 140阅读 0赞

比如：“abcdkkk” 和 “baabcdadabc”，可以找到的最长的公共子序列（连续）是”abcd”,所以最大公共子序列长度（连续）为 4

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#define _for(a,b,c) for(int a=b;a<c;a++)
#define N 256
using namespace std;
int f(const char* s1, const char* s2)
{ 
    int a[N][N];
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    memset(a,0,sizeof(int)*N*N);
    int _max = 0;
    _for(i,0,len1)
        _for(j,0,len2)
            if(s1[i]==s2[j])
            { 
                a[i+1][j+1] = a[i][j] + 1;
                _max = max(_max,a[i+1][j+1]);
            }
    return _max;
}
int main()
{ 
    cout<<f("abcdkkk","baabcdadabc");
    return 0;
}

代码的原理：
两层 for 循环分别表示 len1 和 len2，第一次循环 len2 全部字母对应 len1第一个字母，第二次循环 len2 全部字母对应 len1 第二个字母，直到对应完 len1 全部字母，每对应一个字母 a[i][j] + 1，最后取最大的 a[i][j]