Question

In java what is the full code of a BoyerMoore search algorithm when nested in another class, using only JCF and no non standard packages. The text searching through can only contain printable ASCII characters, and capitalization matters. Also please provide the worst-case time complexity of the search algorithm.

The pattern is a String, and the contents searching is a String.

Answer 1

/* Java Program for Boyer
Moore String Matching Algorithm */


class BMA{
    
     static int num_char = 256;
     
    //A function to get maximum of two integers
     static int max (int a, int b) {
      if (a > b)
        return a;
      else
        return b;
    }

     //The function for Boyer Moore
     static void BMA_Algo( char []str, int size,int match[])
     {
      int i;

      for (i = 0; i < num_char; i++)
           match[i] = -1;

      for (i = 0; i < size; i++)
           match[(int) str[i]] = i;
     }

     // A pattern searching function
     static void search( char text[], char pattern[])
     {
      int x = pattern.length;
      int y = text.length;

      int match[] = new int[num_char];

    
      BMA_Algo(pattern, x, match);

      int s = 0;
      while(s <= (y - x))
      {
          int j = x-1;

          while(j >= 0 && pattern[j] == text[s+j])
              j--;

          if (j < 0)
          {
              System.out.println("Patterns location = " + s);

            
              if (s += (s+x < y))
                 x-match[text[s+x]] ;
              else
                 1;

          }

          else
            
              s += max(1, j - match[text[s+j]]);
      }
     }

     //Main function
    public static void main(String []args) {
       
         Scanner s = new Scanner(System.in);
         char [] text = s.next().toCharArray();
         char [] pattern = s.next().toCharArray();
         search(text, pattern);
    }
}

The Worst case Time Complexity for the above case in BigO(x*y)