title: Approximate String Searching in Java (allowing characters to match more than one option)
body: <p>I have a BNDM search algorithm in java currently but I want to adapt it such that the letter "N" matches any other letter. For example, the string: "NATG" should match "CATG". I am creating a software for nucleotide matching so the sequences will be only A,G,T,C,N where N is any A,G,T,C. </p>
  
  <p>For example: If Sequence: "ATGCN"  and Source: "ATGATGAATGCC". The program should return the index range of the source that matches the sequence. In this case, 7-11. Also if it matches several times, it should print each match. Since the source is often a thousand characters long, I wish to implement a fast searching algorithm. Below is my current BNDM code however this only allows exact matches. </p>
  
  <p>I am not sure if the BNDM algorithm below can be adapted to do this. I am open to a different search algorithm. </p>
  
  <p>I have attached the code below:</p>
  
  <pre><code>import java.util.Scanner;
  
  public class BNDM {
  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int sum = 5;
      String source,pattern;
      System.out.print("Enter sequence:");
      pattern = sc.nextLine(); 
      System.out.print("Enter source:");
      source= sc.nextLine(); 
  
  
      if (pattern.length() == source.length() &amp;&amp; pattern.equals(source)) 
      {
          System.out.println("Sequence = Source");
      }
  
      char[] x = pattern.toCharArray(), y = source.toCharArray();
      int i, j, s, d, last, m = x.length, n = y.length;
      int[] b = new int[65536];
  
      /* Pre processing */
      for (i = 0; i &lt; b.length; i++) {
          b[i] = 0;
      }
      s = 1;
      for (i = m - 1; i &gt;= 0; i--) {
          b[x[i]] |= s;
          s &lt;&lt;= 1;
      }
  
      /* Searching phase */
      j = 0;
      while (j &lt;= n - m) {
          i = m - 1;
          last = m;
          d = ~0;
          while (i &gt;= 0 &amp;&amp; d != 0) {
              d &amp;= b[y[j + i]];
              i--;
              if (d != 0) {
                  if (i &gt;= 0) {
                      last = i + 1;
                  } else {
                      System.out.println("Sequence in Source starting at 
                      position:");
                      System.out.println(j);
                      System.out.println("Sequence:");
                      System.out.println(pattern);
                      System.out.println("Source:");
                      System.out.println(source.substring(j,j+m));
  
                  }
              }
              d &lt;&lt;= 1;
          }
          j += last;
        }
       }
      }
  </code></pre>