Java Program to Implement String Search Algorithm for Short Text Sizes

This is a java program to search string using simple algorithm BoyerMoore.

Here is the source code of the Java Program to Implement the String Search Algorithm for Short Text Sizes. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.setandstring;
  3.  
  4. import java.util.Scanner;
  5.  
  6. class BoyerMoore
  7. {
  8.     private final int BASE;
  9.     private int[]     occurrence;
  10.     private String    pattern;
  11.  
  12.     public BoyerMoore(String pattern)
  13.     {
  14.         this.BASE = 256;
  15.         this.pattern = pattern;
  16.         occurrence = new int[BASE];
  17.         for (int c = 0; c < BASE; c++)
  18.             occurrence[c] = -1;
  19.         for (int j = 0; j < pattern.length(); j++)
  20.             occurrence[pattern.charAt(j)] = j;
  21.     }
  22.  
  23.     public int search(String text)
  24.     {
  25.         int n = text.length();
  26.         int m = pattern.length();
  27.         int skip;
  28.         for (int i = 0; i <= n - m; i += skip)
  29.         {
  30.             skip = 0;
  31.             for (int j = m - 1; j >= 0; j--)
  32.             {
  33.                 if (pattern.charAt(j) != text.charAt(i + j))
  34.                 {
  35.                     skip = Math.max(1, j - occurrence[text.charAt(i + j)]);
  36.                     break;
  37.                 }
  38.             }
  39.             if (skip == 0)
  40.                 return i;
  41.         }
  42.         return n;
  43.     }
  44. }
  45.  
  46. public class StringSearch
  47. {
  48.     public static void main(String[] args)
  49.     {
  50.         Scanner sc = new Scanner(System.in);
  51.         System.out.print("Enter the main string: ");
  52.         String text = sc.nextLine();
  53.         System.out.print("Enter the string to be searched: ");
  54.         String pattern = sc.nextLine();
  55.         BoyerMoore bm = new BoyerMoore(pattern);
  56.         int first_occur_position = bm.search(text);
  57.         System.out.println("The text '" + pattern
  58.                 + "' is first found after the " + first_occur_position
  59.                 + " position.");
  60.         sc.close();
  61.     }
  62. }

Output:

$ javac StringSearch.java
$ java StringSearch
 
Enter the main string: I will soon be working in Redmond USA with Mircosoft.
Enter the string to be searched: soon
The text 'soon' is first found after the 7 position.

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.