#include <iostream>
#include <string>
#include <vector>

using namespace std;

int matchScore = 1;
int mismatchScore = -1;
int gapScore = -2;

int maximum(int a, int b, int c) {
    return max(max(a, b), c);
}

void needlemanWunsch(string seq1, string seq2) {
    int n = seq1.length();
    int m = seq2.length();

    vector<vector<int>> scoreMatrix(n + 1, vector<int>(m + 1, 0));

    // Initialize the first row and column with gap scores
    for (int i = 0; i <= n; i++)
        scoreMatrix[i][0] = i * gapScore;
    for (int j = 0; j <= m; j++)
        scoreMatrix[0][j] = j * gapScore;

    // Fill in the score matrix
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int match = scoreMatrix[i - 1][j - 1] + (seq1[i - 1] == seq2[j - 1] ? matchScore : mismatchScore);
            int deletion = scoreMatrix[i - 1][j] + gapScore;
            int insertion = scoreMatrix[i][j - 1] + gapScore;
            scoreMatrix[i][j] = maximum(match, deletion, insertion);
        }
    }

    // Traceback to find the alignment
    string alignedSeq1 = "";
    string alignedSeq2 = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (scoreMatrix[i][j] == scoreMatrix[i - 1][j - 1] + (seq1[i - 1] == seq2[j - 1] ? matchScore : mismatchScore)) {
            alignedSeq1 = seq1[i - 1] + alignedSeq1;
            alignedSeq2 = seq2[j - 1] + alignedSeq2;
            i--;
            j--;
        } else if (scoreMatrix[i][j] == scoreMatrix[i - 1][j] + gapScore) {
            alignedSeq1 = seq1[i - 1] + alignedSeq1;
            alignedSeq2 = "-" + alignedSeq2;
            i--;
        } else {
            alignedSeq1 = "-" + alignedSeq1;
            alignedSeq2 = seq2[j - 1] + alignedSeq2;
            j--;
        }
    }

    while (i > 0) {
        alignedSeq1 = seq1[i - 1] + alignedSeq1;
        alignedSeq2 = "-" + alignedSeq2;
        i--;
    }

    while (j > 0) {
        alignedSeq1 = "-" + alignedSeq1;
        alignedSeq2 = seq2[j - 1] + alignedSeq2;
        j--;
    }

    cout << "Aligned Sequence 1: " << alignedSeq1 << endl;
    cout << "Aligned Sequence 2: " << alignedSeq2 << endl;
}

int main() {
    string seq1 = "AGTACGCA";
    string seq2 = "TATGC";

    needlemanWunsch(seq1, seq2);

    return 0;
}