import java.io.*;
import java.util.*;

import java.awt.*;

class BruteForce extends java.applet.Applet{

    /**
     * Main method
     * Does most of the work directing
     **/
    public void paint(Graphics g) {
	g.setColor(new Color(3));
	
    }
    
    public void init() {
	try{
	String find_file = "logmatrix.txt";//Args[0];
	String seq_file = "contig.txt";//Args[1];
	
	String coords = "BSP.coords";//Args[2];


	BufferedReader in;
	File inFile = new File (find_file);
	in = new BufferedReader(new FileReader(inFile));
	
	String str = in.readLine();
	Vector find = new Vector();
	
	while((str != null) && (str != "")){
	    //System.out.println(str);
	    find.addElement(str);
	
	    str= in.readLine();
       
	}
	inFile = new File (coords);
	in = new BufferedReader(new FileReader(inFile));
	Vector coord = new Vector();
	str = in.readLine();
	while((str != null) && (str != "")){
	    //System.out.println(str);
	    coord.addElement(new Coords(str));
	
	    str= in.readLine();
       
	}


	inFile = new File (seq_file);
	in = new BufferedReader(new FileReader(inFile));

	//String dump = in.readLine();
	char[] seq = in.readLine().toCharArray();

	
	String strseq = String.valueOf(seq);

       
	char[] current;
	char[] currentrev;

	for (int j = 0; j < find.size(); j++){
	    
	    current = ((String)find.elementAt(j)).toCharArray();
	    
	    char[] temp = (char[])current.clone();
	    currentrev = current;
	    for (int i = 0; i < current.length; i++){
		currentrev[i] = temp[current.length-i-1];
	    }
	    current = temp;

	    System.out.println("Using Motif #"+(j+1)+ " Which is: "+String.valueOf(current));
	    System.out.println("----------------------------------");
	    System.out.println("Forward Strand");
	    
	    String substring;
	    for (int i = 0 ; i <= seq.length-current.length; i++){
		substring = strseq.substring(i,i+current.length);
		//System.out.println(substring);
		if (compare(current, substring.toCharArray())){
		    System.out.print("Match "+ substring +" at "+ i);
		    System.out.println(" At Accession Number:  "+ getName(coord,i)); 
		}
	    }

	    //prepare the reverse comp of the motif
	    char[] currentrevcomp = new char[currentrev.length];
	    for (int i = 0; i < currentrev.length; i++){
		currentrevcomp[i] = convert(currentrev[i]);
	    }


	    System.out.println("Reverse Strand");
	    for (int i = 0 ; i <= seq.length-currentrev.length; i++){
		substring = strseq.substring(i,i+currentrevcomp.length);
	
		if (compare(currentrevcomp, substring.toCharArray())){
		    System.out.print("Match "+ substring +" at "+ i); 
		    System.out.println(" At Accession Number:  "+ getName(coord,i));
		}
	       
		       
	    } 

	    System.out.println();
	    System.out.println();
	}
	}catch (Exception e){
	}
    
    }
    public static boolean compare(char[] a, char[] b){
	boolean match = true;
	
	for (int i = 0; i < a.length; i++){
	    if (match == true){
		if (isSame(a[i],b[i])){
		    match = true;
		}else{
		    match = false;
		}
	    }

	    
	}
	//	System.out.println(String.valueOf(a)+" "+String.valueOf(b)+" is "+match);
	return match;
    }
    public static char convert(char c){
	if (c == 'A') return 'T';
	if(c=='T') return 'A';
	if (c == 'C') return 'G';
	if (c == 'G') return 'C';
	return c;
    }
    public static boolean isSame(char c, char d){
	if ((c == '.') || (c == 'N') || (d == '.') || (d == 'N')){
	    return true;
	}
	if (c == d) return true;
	else return false;


    }
    
    public static String getName(Vector v, int index){
	Coords next;
	String n;
	Coords curr;
	for (int i = 0; i < v.size(); i++){
	    curr =  ((Coords)v.elementAt(i));
	    if (i < v.size()-1){    next = ((Coords)v.elementAt(i+1));}else next = ((Coords)v.elementAt(0)); 
	    if ((!curr.reverse)&&(curr.start<index)&&(curr.end>index)) return curr.name;else
	    if ((curr.reverse)&&(curr.start>index)&&(curr.end<index)) return curr.name;else
	    if ((!curr.reverse)&&(curr.end<index)&&(next.reverse)&&(next.end>index)) return "Between "+curr.name+ " and "+ next.name;
	    if ((!curr.reverse)&&(curr.end<index)&&(!next.reverse)&&(next.start>index)) return "Between "+curr.name+ " and "+ next.name;
	    if ((curr.reverse)&&(curr.start<index)&&(next.reverse)&&(next.end>index)) return "Between "+curr.name+ " and "+ next.name;
	    if ((curr.reverse)&&(curr.start<index)&&(!next.reverse)&&(next.start>index)) return "Between "+curr.name+ " and "+ next.name;
	}
	return "not found";
    }
}

class Coords{
    int start;
    int end;
    String name;
    boolean reverse = false;
    public Coords(String s){
	StringTokenizer st = new StringTokenizer(s);
	name = st.nextToken().trim();
	start = Integer.valueOf(st.nextToken().trim()).intValue();
	end =  Integer.valueOf(st.nextToken().trim()).intValue();	
	if (start < end) reverse = false;
    }

}