package core;

public class NeedlemanWunsch
{
  private int[][] E;
  private int[][] T;
  private String n;
  private String m;
  
  public NeedlemanWunsch(String a, String b)
  {
    this.n = a;this.m = b;
    this.E = new int[this.n.length() + 1][this.m.length() + 1];
    this.T = new int[this.n.length() + 1][this.m.length() + 1];
    initialisiere();
  }
  
  public void initialisiere()
  {
    this.E[0][0] = 0;
    for (int i = 1; i <= this.n.length(); i++)
    {
      this.E[i][0] = 0;
      this.T[i][0] = 1;
    }
    for (int j = 1; j <= this.m.length(); j++)
    {
      this.E[0][j] = 0;
      this.T[0][j] = 2;
    }
  }
  
  private int cost(char a, char b)
  {
    if (a == b) {
      return 1;
    }
    return 0;
  }
  
  public int compare()
  {
    for (int i = 1; i <= this.n.length(); i++) {
      for (int j = 1; j <= this.m.length(); j++) {
        if (this.E[(i - 1)][(j - 1)] + cost(this.n.charAt(i - 1), this.m.charAt(j - 1)) >= this.E[(i - 1)][j])
        {
          this.E[i][j] = (this.E[(i - 1)][(j - 1)] + cost(this.n.charAt(i - 1), this.m.charAt(j - 1)));
          this.T[i][j] = 0;
        }
        else if (this.E[(i - 1)][j] >= this.E[i][(j - 1)])
        {
          this.E[i][j] = this.E[(i - 1)][j];
          this.T[i][j] = 1;
        }
        else
        {
          this.E[i][j] = this.E[i][(j - 1)];
          this.T[i][j] = 2;
        }
      }
    }
    int i = this.n.length();
    int j = this.m.length();
    StringBuffer seq1 = new StringBuffer();
    StringBuffer seq2 = new StringBuffer();
    while ((i > 0) || (j > 0)) {
      switch (this.T[i][j])
      {
      case 0: 
        i--;j--;seq1.append(this.n.charAt(i));seq2.append(this.m.charAt(j)); break;
      case 1: 
        i--;seq1.append(this.n.charAt(i));seq2.append('-'); break;
      case 2: 
        j--;seq1.append('-');seq2.append(this.m.charAt(j));
      }
    }
    return this.E[this.n.length()][this.m.length()];
  }
  
  public static void main(String[] args)
  {
    String a = "Hallo Waldfee";
    String b = "Hola fee";
    NeedlemanWunsch NW = new NeedlemanWunsch(a, b);
    System.out.println(NW.compare());
  }
}