gistfile1.java

package fourth;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
   public static void main(String[] args) throws Exception {
      String t = "aaabcaaaabcaabc";
      String p = "aaaaaaa";
      int distance = 3;

      // String t = "SVLQDRSMPHQEILAADEVLQESEMRQQDMISHDE";
      // String p = "EIQADEVRL";

      if (!(args.length>0 && args[0].equals("xxx"))) {
         BufferedReader br = null;
         br = new BufferedReader(new InputStreamReader(System.in));
         String alphabet = br.readLine();
         p = br.readLine();
         distance = Integer.parseInt(br.readLine());
         t = br.readLine();
      }
      editStringMatch(t, p, distance);

   }

   private static void editStringMatch(String t, String p, int distance) {
      byte[] xArray = t.getBytes();
      byte[] yArray = p.getBytes();
      int[] preArray = new int[yArray.length];
      int[] curArray = new int[yArray.length];

      for (int i = 0; i < preArray.length; i++) {
         preArray[i] = i + 1;
      }

      for (int x = 0; x < xArray.length; x++) {
         for (int y = 0; y < yArray.length; y++) {
            int left, up, cross;
            left = preArray[y] + 1;
            up = y - 1 < 0 ? 1 : curArray[y - 1] + 1;
            cross = (y - 1) < 0 ? 0 : preArray[y - 1];
            if (xArray[x] != yArray[y]) {
               cross = Integer.MAX_VALUE;
            }
            curArray[y] = Math.min(Math.min(left, up), cross);
            // System.out.print(curArray[y] + " ");

         }
         // System.out.println();
         if (curArray[curArray.length - 1] <= distance)
            System.out.println(x);
         System.arraycopy(curArray, 0, preArray, 0, curArray.length);
      }
   }

   private static void approxStringMatch(String t, String p, int distance) {
      char[] xArray = t.toCharArray();
      char[] yArray = p.toCharArray();
      int[] preArray = new int[yArray.length];
      int[] curArray = new int[yArray.length];

      for (int i = 0; i < preArray.length; i++) {
         preArray[i] = distance + 1;
      }

      for (int x = 0; x < xArray.length; x++) {
         for (int y = 0; y < yArray.length; y++) {
            if (xArray[x] == yArray[y]) {
               curArray[y] = (y - 1) < 0 ? 0 : preArray[y - 1];
            } else {
               curArray[y] = ((y - 1) < 0 ? 0 : preArray[y - 1]) + 1;
            }
         }
         if (curArray[curArray.length - 1] <= distance)
            System.out.println(x);
         preArray = curArray;
      }
   }
}