欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长公共子序列模板

程序员文章站 2024-01-14 13:45:22
...
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1011;
int dp[Maxn][Maxn];
int main(){
    string A,B;
    cin >> A >> B;
    int a = A.length(),b = B.length();
    int maxn = -1;
    for( int i = 1; i <= A.length(); i++ ){
        for( int j = 1; j <= B.length(); j++ ){
            if( A[i-1] == B[j-1] ){
                dp[i][j] = dp[i-1][j-1]+1;
            }else if( dp[i][j-1] > dp[i-1][j] ){
                dp[i][j] = dp[i][j-1];
            }else{
                dp[i][j] = dp[i-1][j];
            }
            maxn = max( maxn,dp[i][j] );
        }
    }
    vector<char> v;
    for( int i = a,j = b; i >= 1 && j >= 1; ){
        if( A[i-1] == B[j-1] ){
            v.push_back(A[i-1]);
            i--,j--;
        }else{
            if( dp[i][j-1] > dp[i-1][j] ){
                j--;
            }else{
                i--;
            }
        }
    }
    reverse(v.begin(),v.end());
    for(auto x:v){
        cout << x;
    }
}

 用python实现了一下,吐血了,一个浅拷贝弄得我要死

python定义数组不可以用dp = [[0]*1010]*1010,会有浅拷贝,具体的可以百度一下

下面是python的代码

dp = [([0]*1010) for i in range(1010)]
A = list(raw_input())
B = list(raw_input())
a = len(A)
b = len(B)
for i in range(1,a+1):
    for j in range(1,b+1):
        if A[i-1] == B[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max( dp[i-1][j],dp[i][j-1] )


val = []
i = a
j = b
while i >= 1 and j >= 1:
    if A[i-1] == B[j-1]:
        val.append(A[i-1])
        i -= 1
        j -= 1
    else:
        if dp[i][j-1] > dp[i-1][j]:
            j -= 1
        else:
            i -= 1
print "".join(val[::-1])