TheAlgorithms · siriak · Jun 11, 2025 · Jun 8, 2025 · Jun 8, 2025 · Jun 8, 2025
@@ -0,0 +1,58 @@
+package com.thealgorithms.searches;
+
+/**
+ * Boyer-Moore string search algorithm.
+ * Efficient algorithm for substring search.
+ * https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm
+ */
+public class BoyerMoore {
+
+    private final int radix; // Radix (number of possible characters)
+    private final int[] right; // Bad character rule table
+    private final String pattern;
+
+    public BoyerMoore(String pat) {
+        this.pattern = pat;
+        this.radix = 256;
+        this.right = new int[radix];
+
+        for (int c = 0; c < radix; c++) {
+            right[c] = -1;
+        }
+
+        for (int j = 0; j < pat.length(); j++) {
+            right[pat.charAt(j)] = j;
+        }
+    }
+
+    public int search(String text) {
+        if (pattern.isEmpty()) {
+            return 0;
+        }
+
+        int m = pattern.length();
+        int n = text.length();
+
+        int skip;
+        for (int i = 0; i <= n - m; i += skip) {
+            skip = 0;
+            for (int j = m - 1; j >= 0; j--) {
+                char txtChar = text.charAt(i + j);
+                char patChar = pattern.charAt(j);
+                if (patChar != txtChar) {
+                    skip = Math.max(1, j - right[txtChar]);
+                    break;
+                }
+            }
+            if (skip == 0) {
+                return i; // Match found
+            }
+        }
+
+        return -1; // No match
+    }
+
+    public static int staticSearch(String text, String pattern) {
+        return new BoyerMoore(pattern).search(text);
+    }
+}
@@ -0,0 +1,55 @@
+package com.thealgorithms.searches;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class BoyerMooreTest {
+
+    @Test
+    public void testPatternFound() {
+        BoyerMoore bm = new BoyerMoore("ABCDABD");
+        String text = "ABC ABCDAB ABCDABCDABDE";
+        int index = bm.search(text);
+        assertEquals(15, index);
+    }
+
+    @Test
+    public void testPatternNotFound() {
+        BoyerMoore bm = new BoyerMoore("XYZ");
+        String text = "ABC ABCDAB ABCDABCDABDE";
+        int index = bm.search(text);
+        assertEquals(-1, index);
+    }
+
+    @Test
+    public void testPatternAtBeginning() {
+        BoyerMoore bm = new BoyerMoore("ABC");
+        String text = "ABCDEF";
+        int index = bm.search(text);
+        assertEquals(0, index);
+    }
+
+    @Test
+    public void testPatternAtEnd() {
+        BoyerMoore bm = new BoyerMoore("CDE");
+        String text = "ABCDEFGCDE";
+        int index = bm.search(text);
+        assertEquals(2, index); // Primera ocurrencia de "CDE"
+    }
+
+    @Test
+    public void testEmptyPattern() {
+        BoyerMoore bm = new BoyerMoore("");
+        String text = "Hello world";
+        int index = bm.search(text);
+        assertEquals(0, index);
+    }
+
+    @Test
+    public void testStaticSearchMethod() {
+        String text = "ABCDEFGCDE";
+        int index = BoyerMoore.staticSearch(text, "CDE");
+        assertEquals(2, index); // Primera ocurrencia de "CDE"
+    }
+}