import java.util.*;

public class matchwide
{
    private String seq1 = "";           //the source sequence
    private String seq2 = "";           //the recognition sequence
    private int len1 = 0;
    private int len2 = 0;
    private Stack stack = new Stack();
    private Stack temp = new Stack();

    public matchwide (String s1, String s2)
    {
        seq1 = s1;
        seq2 = s2;
        len1 = seq1.length();
        len2 = seq2.length();
    }

    //a method the check whether two nucleotides match each other
    private boolean checkchar (char ch1, char ch2)
    {
        //ch1 is in recognition sequence, ch2 is in source sequence
        if (ch1 == 'A') 
        {
            if (ch2 == 'A')
                return true;
        }

        else if (ch1 == 'T')
        {
            if (ch2 == 'T')
                return true;
        }

        else if (ch1 == 'G')
        {
            if (ch2 == 'G')
                return true;
        }

        else if (ch1 == 'C')
        {
            if (ch2 == 'C')
                return true;
        }

        else if (ch1 == 'R')
        {
            if ((ch2 == 'A') || (ch2 == 'G') || (ch2 == 'R'))
                return true;
        }

        else if (ch1 == 'K')
        {
            if ((ch2 == 'G') || (ch2 == 'T') || (ch2 == 'K'))
                return true;
        }

        else if (ch1 == 'Y')
        {
            if ((ch2 == 'C') || (ch2 == 'T') || (ch2 == 'Y'))
                return true;
        }

        else if (ch1 == 'S')
        {
            if ((ch2 == 'C') || (ch2 == 'G') || (ch2 == 'S'))
                return true;
        }

        else if (ch1 == 'M')
        {
            if ((ch2 == 'A') || (ch2 == 'C') || (ch2 == 'M'))
                return true;
        }

        else if (ch1 == 'W')
        {
            if ((ch2 == 'A') || (ch2 == 'T') || (ch2 == 'W'))
                return true;
        }

        else if (ch1 == 'H')
        {
            if ((ch2 == 'A') || (ch2 == 'C') || (ch2 == 'T') ||
                (ch2 == 'M') || (ch2 == 'W') || (ch2 == 'Y') || (ch2 == 'H'))
                return true;
        }

        else if (ch1 == 'V')
        {
            if ((ch2 == 'A') || (ch2 == 'C') || (ch2 == 'G') ||
                (ch2 == 'R') || (ch2 == 'S') || (ch2 == 'M') || (ch2 == 'V'))
                return true;
        }

        else if (ch1 == 'B')
        {
            if ((ch2 == 'T') || (ch2 == 'C') || (ch2 == 'G') ||
                (ch2 == 'K') || (ch2 == 'S') || (ch2 == 'Y') || (ch2 == 'B'))
                return true;
        }

        else if (ch1 == 'D')
        {
            if ((ch2 == 'T') || (ch2 == 'A') || (ch2 == 'G') ||
                (ch2 == 'R') || (ch2 == 'K') || (ch2 == 'W') || (ch2 == 'D'))
                return true;
        }

        else if (ch1 == 'N')
        {
            if ((ch2 == 'T') || (ch2 == 'A') || (ch2 == 'G') || (ch2 == 'C') ||
                (ch2 == 'R') || (ch2 == 'K') || (ch2 == 'H') || (ch2 == 'V') ||
                (ch2 == 'N') || (ch2 == 'Y') || (ch2 == 'S') || (ch2 == 'M') ||
                (ch2 == 'W') || (ch2 == 'B') || (ch2 == 'D'))
                return true;
        }

        return false;
    }

    //a method to check whether and where the two sequences match each other
    private boolean checkseq (int p)
    {
        int p1 = 0;

        //move forwards and compare one by one
        for (int i=0; i<len2; i++)
        {
            p1 = p + i;
            if (checkchar(seq2.charAt(i), seq1.charAt(p1)) == false)
                return false;
        }

        return true;
    }

    //a method to check whether the enzyme serves as a candidate
    public boolean matching ()
    {
         //starting comparing from the very beginning
         for (int i=0; i<(len1-len2); i++)
         {
             if (checkseq(i) == true)
                 temp.push(java.lang.Integer.toString(i+1));
         }

         //reverse the order to stack content
         while (temp.empty() != true)
             stack.push(temp.pop());

         if (stack.empty() != true) return true;
         else return false;
    }

    //a method to get all potential cutting positions one by one
    public String get()
    {
        String tempstr = "";
        if (stack.empty() != true)
        {
            tempstr = (String)stack.pop();
            return tempstr;
        }
        else return null;
    }
}