[LUOGU] P2543 [AHOI2004]奇怪的字符串

LCS

//Writer:GhostCai && His Yellow Duck

#include<iostream>

#include<cstring>

#define MAXN 5000

using namespace std;

char s[MAXN],t[MAXN];

int lens,lent;

int f[MAXN][MAXN];

int main() {

    cin>>s+1>>t+1;

    memset(f,0,sizeof(f));

    lens=strlen(s+1);

    lent=strlen(t+1);

    for(int i=1; i<=lens; i++) {

        for(int j=1; j<=lent; j++) {

            if(s[i]==t[j]) {

                f[i][j]=f[i-1][j-1]+1;

            } else {

                f[i][j]=max(f[i-1][j],f[i][j-1]);

            }

        }

    }

    cout<<f[lens][lent]<<endl;

    return 0;

}

巴特西

[LUOGU] P2543 [AHOI2004]奇怪的字符串

最新文章

热门文章