public class bin_vs_lin {
  public static void main(String args[]) {
     String text1 = "";
     String text2 = "";
     int result;
     
     int n = Integer.parseInt(args[0]);
     int repeats = 100;
     int charcode;
     int answer;
     long ms_start, ms_end;
     String correct;

     // Create a random string of 'n' letters.
     while (text1.length() < n) {
       charcode = 32 + (int) (Math.random() * (127 - 32));
       text1 = text1 + String.valueOf((char) charcode) + text1;
     }
     text1 = text1.substring(0, n);

     // Create another random string which differs from the first by one letter inserted.
     answer = (int) (Math.random() * n);
     text2 = text1.substring(0, answer) + "\t" + text1.substring(answer);
     
     // Linear search
     result = -1;
     ms_start = System.currentTimeMillis();
     for (int x = 0; x < repeats; x++) {
       for (int i = 0; i < text1.length(); i++) {
         if (text1.charAt(i) != text2.charAt(i)) {
           result = i;
           break;
         }
       }
     }
     ms_end = System.currentTimeMillis();
     
     correct = (result == answer) ? "OK" : "FAIL";
     System.out.println("Linear: " + ((double)(ms_end - ms_start) / (double) repeats) + "ms (" + correct + ")");

     // Binary search
     result = -1;
     ms_start = System.currentTimeMillis();
     for (int x = 0; x < repeats; x++) {
       result = diff_commonPrefix(text1, text2);
     }
     ms_end = System.currentTimeMillis();     

     correct = (result == answer) ? "OK" : "FAIL";
     System.out.println("Binary: " + ((double)(ms_end - ms_start) / (double) repeats) + "ms (" + correct + ")");
  }

  /**
   * Trim off common prefix
   * @param text1 First string
   * @param text2 Second string
   * @return The number of characters common to the start of each string.
   */
  static int diff_commonPrefix(String text1, String text2) {
    // Quick check for common null cases.
    if (text1.length() == 0 || text2.length() == 0 ||
        text1.charAt(0) != text2.charAt(0)) {
      return 0;
    }
    // Binary search.
    int pointermin = 0;
    int pointermax = Math.min(text1.length(), text2.length());
    int pointermid = pointermax;
    int pointerstart = 0;
    while (pointermin < pointermid) {
      if (text1.regionMatches(pointerstart, text2, pointerstart,
          pointermid - pointerstart)) {
        pointermin = pointermid;
        pointerstart = pointermin;
      } else {
        pointermax = pointermid;
      }
      pointermid = (pointermax - pointermin) / 2 + pointermin;
    }
    return pointermid;
  }
}