ntttask

#include <bits/stdc++.h>

using namespace std;


int main() {
    string s1, s2;
    cout << "s1: ";
    cin >> s1;
    cout << "s2: ";
    cin >> s2;
    int n = s1.length(), m = s2.length();
    int dp[n+1][m+1] = {0};

    // penalties
    int gap = 2; // penalty for matching a chartacter to a gap
    int mis = 3; // penalty for matching a character to a different character


    for (int i = 1; i < n+1; i++)
        dp[i][0] = i*gap;

    for (int i = 1; i < m+1; i++)
        dp[0][i] = i*gap;

    for (int i = 1; i < n+1; i++)
        for (int j = 1; j < m+1; j++)
        {
            if ( s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min({dp[i][j-1] + gap, dp[i-1][j] + gap, dp[i-1][j-1] + mis});
        }

    string s1_out="", s2_out="";

    int i=n, j=m;

    cout << "Gap Score: " << dp[n][m] << endl;

    while (i>0 && j > 0) {
        if (s1[i-1] == s2[j-1] || dp[i-1][j-1] + mis == dp[i][j]) {
            s1_out += s1[i-1];
            s2_out += s2[j-1];
            i--; j--;
        }
        else if (dp[i][j-1] + gap == dp[i][j]) {
            s1_out += '-';
            s2_out += s2[j-1];
            j--;
        }
        else if (dp[i-1][j] + gap == dp[i][j]) {
            s1_out += s1[i-1];
            s2_out += '-';
            i--;
        }
    }

    while (i--){
        s1_out += s1[i];
    }

    while (j--) {
        s2_out += s2[j];
    }

    while (s1_out.length() > s2_out.length()) {
        s2_out += '-';
    }

    while (s2_out.length() > s1_out.length()) {
        s1_out += '-';
    }

    reverse(s1_out.begin(), s1_out.end());
    reverse(s2_out.begin(), s2_out.end());
    cout << s1_out << '\n' << s2_out << endl;
}