#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {return a > b ? a : b;}
char* strrev(char *s)
{
    int j,k,c;
    for(k=0;s[k] != 0;k++);
    for(j=0,k--;j<k;j++,k--) {
        c = s[j];
        s[j] = s[k];
        s[k] = c;
    }
    return s;
}

int** swmatrix(const char* str1, const char* str2)
{
    int** a = (int**) calloc(strlen(str1)+1, sizeof(int*));
    for(int i = 0; i <= strlen(str1); i++) {
        a[i] = (int*) calloc(strlen(str2)+1, sizeof(int));
    }
    for(int i = 1; i <= strlen(str1); i++)
    {
        for(int j = 1; j <= strlen(str2); j++)
        {
            a[i][j] = max(a[i][j], a[i-1][j-1] + ((str1[i-1] == str2[j-1]) ? 2 : -1)); // match/ mismatch
            a[i][j] = max(a[i][j], a[i-1][j] - 1); // deletion
            a[i][j] = max(a[i][j], a[i][j-1] - 1); // insertion
        }
    }
    return(a);
}

void swtraceback(int imax, int jmax, int** a, const char* str1, const char* str2, char* l1, char* l2, char *l3)
{
    int i = imax, j = jmax;
    while(a[i][j])
    {
        if(a[i][j] == a[i-1][j-1] + ((str1[i-1] == str2[j-1]) ? 2 : -1))
        {
            // match/ mismatch
            *l1++ = str1[i-1];
            *l2++ = (str1[i-1] == str2[j-1]) ? '|' : ' ';
            *l3++ = str2[j-1];
            i--; j--;
        }
        else if(a[i][j] == a[i-1][j] - 1)
        {
            // deletion
            *l1++ = str1[i-1];
            *l2++ = ' ';
            *l3++ = '-';
            i--;
        }
        else if(a[i][j] == a[i][j-1] - 1)
        {
            // insertion
            *l1++ = '-';
            *l2++ = ' ';
            *l3++ = str2[j-1];
            j--;
        }
    }
    *l1 = *l2 = *l3 = '\0';
}

int main()
{
    const char* str1 = "XXXEHEAGAWGHEEW";
    const char* str2 = "PAWHEAEG";

    int** matrix = swmatrix(str1, str2);
    printf("        ");
    for(int j = 0; j <= strlen(str2); j++)
        printf("%3c ", str2[j]);
    printf("\n");
    for(int i = 0; i <= strlen(str1); i++)
    {
        if(i)
            printf("%3c ", str1[i-1]);
        else
            printf("    ");
        for(int j = 0; j <= strlen(str2); j++)
            printf("%3i ", matrix[i][j]);
        printf("\n");
    }
    int mmax = 0, imax, jmax;
    for(int i = 1; i <= strlen(str1); i++)
    {
        for(int j = 1; j <= strlen(str2); j++)
        {
            if(matrix[i][j]>mmax)
            {
                mmax = matrix[i][j];
                imax = i;
                jmax = j;
            }
        }
    }
    printf("Max\t%2i\n", mmax);
    char* line1 = (char*) calloc(imax+jmax+1, sizeof(char));
    char* line2 = (char*) calloc(imax+jmax+1, sizeof(char));
    char* line3 = (char*) calloc(imax+jmax+1, sizeof(char));
    swtraceback(imax, jmax, matrix, str1, str2, line1, line2, line3);
    printf("%s\n%s\n%s\n", strrev(line1), strrev(line2), strrev(line3));

    return(0);
}