import java.util.Random;

public class SpeedMeUp {
   public static void main(String[] args) {
      byte[][] patternSet = makePatterns(12000, 4, 10);
      byte[][] tests = makePatterns(12000, 2, 10);
      int best = -1, newBest;
      long start;
           
      // Speed up the rest of the program, improving it by a factor of at least
      // 50, as measured by the reported elapsed time.  (Close ties will be 
      // broken by running on larger datasets.)  A speedup of over 100 is 
      // possible.  Prizes to the fastest 3 implementations that improve by 
      // at least a factor of 50, on the data used here.  
      //
      // Do not modify this original -- keep it for reference.  Copy it into
      // a file "MeSpedUp.java" and improve that one.
      //
      // Do not make drastic changes to the code, nor introduce entirely new
      // algorithms (e.g. KMP or other such) -- all improvements must be
      // incremental, and must not eliminate or significantly change any of
      // the methods, though you may modestly alter method signatures and
      // preconditions.  Do not write code that is hardwired to the particulars
      // of the test data generated here.
      
      start = System.currentTimeMillis();
      
      for (int i = 0; i < tests.length; i++) {
         if ((newBest = highestOffset(tests[i], patternSet)) > best)
            best = newBest;
      }
      System.out.println("Best was " + best);
      System.out.println("Elapsed time " + (System.currentTimeMillis() - start));
   }

   // Return the highest offset at which "toFind" first appears as a 
   // substring of any string in "dictionary", or -1 if toFind never 
   // appears as a substring.
   public static int highestOffset(byte[] toFind, byte[][] pSet) {
      int best = -1, newBest;
      
      for (int i = 0; i < pSet.length; i++) {
         newBest = -1;
         for (int j = 0; j < pSet[i].length; j++)
            if (testMatch(toFind, pSet[i], j))
               newBest = j;
         if (newBest > best)
            best = newBest;
      }
      return best;
   }
   
   // Determine whether "toFind" matches "pattern", starting at offset "offs".
   public static boolean testMatch(byte[] toFind, byte[] pattern, int offs) {
      int i;
      
      for (i = 0; i < toFind.length && i+offs < pattern.length; i++)
         if (toFind[i] != pattern[i+offs])
            break;
      return i == toFind.length;
   }
   
   // Randomly create an array of "dim" patterns, with patterns having
   // length between min and max 
   public static byte[][] makePatterns(int dim, int min, int max) {
      StringBuilder str;
      byte[][] pSet = new byte[dim][];
      Random rnd = new Random(1);
      
      for (int d = 0; d < pSet.length; d++) {
         pSet[d] = new byte[rnd.nextInt(max - min + 1) + min];
         rnd.nextBytes(pSet[d]);
      }
      return pSet;
   }
}