using System;

public class bin_vs_lin {
  public static void Main(string[] args) {
    Random rand = new Random();
    string text1 = "";
    string text2 = "";
    int n = Convert.ToInt32(args[0]) * 1000;
    int repeats = 100;
    
    // Create a random string of 'n' letters.
    while (text1.Length < n) {
      int charcode = rand.Next(32, 127);
      text1 = text1 + Convert.ToChar(charcode) + text1;
    }
    text1 = text1.Substring(0, n);

    // Create another random string which differs from the first by one letter inserted.
    int answer = rand.Next(0, n);
    text2 = text1.Insert(answer, "\t");

    // Linear search.
    int result = -1;
    DateTime ms_start = DateTime.Now;
    for(int x = 0; x < repeats; x++) {
      for(int i = 0; x < text1.Length; i++) {
        if (text1[i] != text2[i]) {
          result = i;
          break;
        }
      }
    }
    DateTime ms_end = DateTime.Now;

    string correct = (result == answer) ? "OK" : "FAIL";
    Console.WriteLine("Linear: " + (ms_end - ms_start) + " (" + correct + ")");
    
    // Binary search
    result = -1;
    ms_start = DateTime.Now;
    for (int x = 0; x < repeats; x++) {
      result = diff_commonPrefix(text1, text2);
    }
    ms_end = DateTime.Now;

    correct = (result == answer) ? "OK" : "FAIL";
    Console.WriteLine("Binary: " + (ms_end - ms_start) + " (" + 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[0] != text2[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.Substring(pointerstart, pointermid - pointerstart) ==
          text2.Substring(pointerstart, pointermid - pointerstart)) {
        pointermin = pointermid;
        pointerstart = pointermin;
      } else {
        pointermax = pointermid;
      }
      pointermid = (pointermax - pointermin) / 2 + pointermin;
    }
    return pointermid;
  }
}