Перейти к содержанию

Реализации алгоритмов/Задача о наибольшей общей подпоследовательности

Материал из Викиучебника — открытых книг для открытого мира

Реализация задачи о наибольшой общей подпоследовательности на разных языках программирования.

 
//LCS
#include <iostream>

using namespace std;

string s_1, s_2; //строки

int main() {
    cin>>s_1>>s_2;
    
    int m = s_1.size();
    int n = s_2.size();
    
    vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
    
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            (s_1[i] = s_2[j]) ? dp[i][j] = dp[i - 1][j - 1] + 1
                              : dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    cout<<dp[m][n]<<"\n";

    return 0;
}