program NW
    implicit none

    !Os dois genes a serem analizados:
    character (LEN=1000), parameter :: gene1 = "ACG" !LINHA |
    character (LEN=1000), parameter :: gene2 = "GC" !COLUNA _
    integer, parameter           :: m = len_trim(gene1)
    integer, parameter           :: n = len_trim(gene2)

    !A matriz a ser trabalhada
    real, dimension(n+1,m+1)         :: F !F = 4x10

    !pontuações
    integer, parameter :: gap = -4
    integer, parameter :: match = 5
    integer, parameter :: mismatch = -3

    !backtrack ou seila o nome
    integer :: backt

    !Variaveis auxiliares
    integer :: i = 1
    integer :: j = 1
    integer :: escolha1
    integer :: escolha2
    integer :: escolha3

    !TEMPO
    real*4  :: tempo

    tempo = SECNDS(0.0)

    !Preenchendo a F
    ! i =1
    do i =1, n+1
        F(i,1) = (i-1)*gap
    end do
    ! j = 1
    do j = 1, m+1
        F(1,j) = (j-1)*gap
    end do
    ! Todo o resto da F
    do i=2, n+1
        do j=2, m+1
            if (gene1(j-1:j-1) == gene2(i-1:i-1)) then
               escolha1 = F(i-1,j-1) + match
            else
               escolha1 = F(i-1,j-1) + mismatch
            end if
            escolha2 = F(i-1,j) + gap
            escolha3 = F(i,j-1) + gap
            F(i,j) = max(escolha1, escolha2, escolha3)
        end do
    end do

    i = i-1
    j = j-1

    backt = 0

    do while ((i >= 1 .AND. j >= 1) .AND. .NOT.(i == j .AND. j == 1))
        if (gene1(j-1:j-1) == gene2(i-1:i-1)) then
           escolha1 = F(i-1,j-1) + match
        else
           escolha1 = F(i-1,j-1) + mismatch
        end if
        escolha2 = F(i-1,j) + gap
        escolha3 = F(i,j-1) + gap

        if (max(escolha1, escolha2, escolha3) == escolha1) then
            if (gene1(j-1:j-1) == gene2(i-1:i-1)) then
                backt = backt + match
            else
                backt = backt + mismatch
            end if

           i = i-1
           j = j-1
        else if (max(escolha1, escolha2, escolha3) == escolha2) then
           backt = backt + gap

           i = i-1
        else
           backt = backt + gap

           j = j-1
        end if
    end do

    !Arquivo para ser lido porque a formatação do fortran é mt ruim

    tempo = SECNDS(tempo)

    !print
    print *,"O backtrack eh: ", backt
    print *,"O tempo eh: ", tempo


end program