/* * To change this template, choose Tools | Templates * and open the template in the editor. */
package dynamic_prog;
import java.util.Scanner;
import java.io.*;
import java.io.FileReader;
import java.nio.file.Files;
import java.util.*;
import java.lang.String;
import java.nio.charset.Charset;
import java.nio.file.*;
import java.util.Collections;
import java.lang.Exception;
/** * * @author Hira */publicclass Dynamic_Prog {
    
   // Path p=Paths.get("seq.txt");//Charset charset = Charset.forName("US-ASCII");// BufferedReader reader = Files.newBufferedReader(p, charset)) {//  String line = null;// while ((line = reader.readLine()) != null) {//   System.out.println(line);// }privatestatic String a=" GGATCGA";
    privatestatic String b=" GAATTCAGTTA";
    privatestatic List<String>trace=new ArrayList<String>();
    privatestatic String na,nb;
    privatestaticint[][] arr = newint[a.length()][b.length()];
    privatestaticint match,mismatch,gap;
    /**     * @param args the command line arguments     */publicstaticvoid main(String[] args) {
     
    System.out.print(a.charAt(0));
       Scanner in=new Scanner(System.in);
       System.out.println("set scores:");
       System.out.println("Enter score for match:");
       match=in.nextInt();
       System.out.println("Enter score for mismatch(-ive value):");
       mismatch=in.nextInt();
       System.out.println("Enter gap penalty"); 
       gap=in.nextInt();
       
        System.out.println(a);
       
       for(int i=0, j=0;j<b.length();j++)
           arr[i][j]=j*gap;
       
     
       
       for (int i=1,j=0;i<a.length();i++)
           arr[i][j]=gap*i;
     
      
       for (int i=0;i<a.length();i++){
          for(int j=0;j<b.length();j++)
               System.out.print(arr[i][j]+" ");
          System.out.println();
       }
           
       for (int i=1;i<a.length();i++)
           for(int j=1;j<b.length();j++)
                arr[i][j]=max(i,j);
       System.out.println("trace list");
       System.out.println(trace);
       // for (int i=0;i<a.length();i++){// for(int j=0;j<b.length();j++)// System.out.print(arr[i][j]+" ");// System.out.println();
           
       
               traceback();
               
    
    }
    
   publicstaticint max(int i,int j){
       int x,y,z;
       String p,o,t; 
       List<Integer>l=new ArrayList<Integer>();
    //   List<Integer>index=new ArrayList<Integer>();if(a.charAt(i)==b.charAt(j)){
                            x=arr[i-1][j-1]+match;
                            l.add(x);
                            p=i-1+":"+(j-1)+"";
                            
                      }
                      else{
                             x=arr[i-1][j-1]+mismatch;
                             l.add(x);
                             p=i-1+":"+(j-1)+"";
                          }
                     y=arr[i][j-1]+gap;
                     l.add(y);
                     o=i+":"+(j-1)+"";
                     z=arr[i-1][j]+gap;
                     l.add(z);
                     t=i-1+":"+(j)+"";
                     int max=Collections.max(l);    
                    // System.out.println(l);// System.out.println(max);if(max==y)
                     {
                         //trace.add(o);
                         trace.add("h");
                         String n=max+"";
                        // trace.add(n);
                     }
                     elseif(max==z)
                     {
                        ////trace.add(t);
                        trace.add("v");
                        String n=max+"";
                        // trace.add(n);
                     }
                             
                     else{
                      // trace.add(p);
                       trace.add("d"); 
                       String n=max+"";
                       // trace.add(n);
                     }       
                trace.toString();
                
       return max;
           }
   
    publicstaticvoid traceback(){
        
         List<String>x=new ArrayList<String>();
         List<String>y=new ArrayList<String>();
         a=a.trim();
         b=b.trim();
      //   Collections.reverse(a);//Collections.reverse(b);    
         System.out.println(a);
         int i=a.length()-1;
         int j=b.length()-1;
        // List<String>a1=new ArrayList<String>();// List<String>b1=new ArrayList<String>();
          System.out.println(i);
           System.out.println(j);
           String h;
           String   c;
           char t,r;
        //for(int i=l;i>=l;){// for(int j=k;j>=k;){//do{for(int w=trace.size()-1;w>=0;)
               {
                 // if(trace.get(w)=="h")
                   {
                        x.add("_");                       
                        //trace.remove(w);// a=a.substring(0, i);
                       c= b.charAt(j)+"";
                        y.add(c);
                        j--; 
                        w--;
                       // break;
               }
                  elseif(trace.get(w)=="v"){
                      y.add("_");
                      //trace.remove(w);
                       h=a.charAt(i)+"";
                       x.add(h);
                       i--;
                       w=w-b.length();
                      //a=a.substring(0, i);// b=b.substring(0, j); // break;
                  } 
                  elseif(trace.get(w)=="d")
                  {
                     // try{
                      
                      t=a.charAt(i);
                      h=t+"";
                      x.add(h);
                       c=b.charAt(j)+"";
                     y.add(c); 
                     // trace.remove(w);//a=a.substring(0, i);// b=b.substring(0, j); 
                      j--;
                      i--;
                      w=w-(b.length()-1);
                     // break;//  }catch(Exception e)// {//System.err.println("caught exception");// }
                  }
                     // else//{// }
        }
       // }//while(i>-1||j>-1);
         

       Collections.reverse(x);
       Collections.reverse(y);        
       // String f=x.toString();// String o=y+"";
       
       System.out.println("X"); 
       System.out.println(x);
       System.out.println("y list");
       System.out.println(y);
       System.out.println(a);
    }
}