class SearchUtil
{
   // Boyer Moore algorithm copyright by Michael Lecuyer 1998.  Slight modification below.

   private static final int MAXCHAR = 256;   // Maximum chars in character set.
   private byte pat[];      // Byte representation of pattern
   private int patLen;
   private int partial;   // Bytes of a partial match found at the end of a text buffer

   private int skip[];      // Internal BM table
   private int d[];        // Internal BM table

   SearchUtil()
   {
      skip = new int[MAXCHAR];
      d = null;
   }

   public int boyer_mooreSearch(String text, String pattern)
   {
      byte[] byteText = text.getBytes();
      compile(pattern);

      return search(byteText, 0, text.length());
   }

   public int linearSsearch(String text, String pattern)
   {
      int textLength = text.length();
      int patternLength = pattern.length();

      for(int i = 0; i <= textLength - patternLength; i++)
      {       String subPattern = text.substring(i, i + patternLength);
            if (pattern.equals(subPattern))
            {   return i;
            }
      }

      return -1;
   }

   public void compile(String pattern)
   {
      pat = pattern.getBytes();
      patLen = pat.length;

      int j, k, m, t, t1, q, q1;
      int f[] = new int[patLen];
      d = new int[patLen];

      m = patLen;
      for (k = 0; k < MAXCHAR; k++)
         skip[k] = m;

      for (k = 1; k <= m; k++)
      {
         d[k-1] = (m << 1) - k;
         skip[pat[k-1]] = m - k;
      }

      t = m + 1;
      for (j = m; j > 0; j--)
      {
         f[j-1] = t;
         while (t <= m && pat[j-1] != pat[t-1])
         {
            d[t-1] = (d[t-1] < m - j) ? d[t-1] : m - j;
            t = f[t-1];
         }
         t--;
      }
      q = t;
      t = m + 1 - q;
      q1 = 1;
      t1 = 0;

      for (j = 1; j <= t; j++)
      {
         f[j-1] = t1;
         while (t1 >= 1 && pat[j-1] != pat[t1-1])
            t1 = f[t1-1];
         t1++;
      }

      while (q < m)
      {
         for (k = q1; k <= q; k++)
            d[k-1] = (d[k-1] < m + q - k) ? d[k-1] : m + q - k;
         q1 = q + 1;
         q = q + t - f[t-1];
         t = f[t-1];
      }
   }


   /**
   * Search for the compiled pattern in the given text.
   * A side effect of the search is the notion of a partial
   * match at the end of the searched buffer.
   * This partial match is helpful in searching text files when
   * the entire file doesn't fit into memory.
   *
   * @param text Buffer containing the text
   * @param start Start position for search
   * @param length Length of text in the buffer to be searched.
   *
   * @return position in buffer where the pattern was found.
   * @see patialMatch
   */
   public int search(byte text[], int start, int length)
   {
      int textLen = length + start;
      partial = -1;   // assume no partial match

      if (d == null)
         return -1;   // no pattern compiled, nothing matches.

      int m = patLen;
      if (m == 0)
         return 0;

      int k, j = 0;
      int max = 0;   // used in calculation of partial match. Max distand we jumped.

      for (k = start + m - 1; k < textLen;)
      {
         for (j = m - 1; j >= 0 && text[k] == pat[j]; j--)
            k--;

         if (j == -1)
            return k + 1;

         int z = skip[text[k]];
         max = (z > d[j]) ? z : d[j];
         k += max;
      }

      if (k >= textLen && j > 0)   // if we're near end of buffer --
      {
         partial = k - max - 1;

         return -1;   // not a real match
      }

      return -1;   // No match
   }


   /**
   * Returns the position at the end of the text buffer where a partial match was found.
   * <P>
   * In many case where a full text search of a large amount of data
   * precludes access to the entire file or stream the search algorithm
   * will note where the final partial match occurs.
   * After an entire buffer has been searched for full matches calling
   * this method will reveal if a potential match appeared at the end.
   * This information can be used to patch together the partial match
   * with the next buffer of data to determine if a real match occurred.
   *
   * @return -1 the number of bytes that formed a partial match, -1 if no
   * partial match
   */
   public int partialMatch()
   {
      return partial;
   }

}