Repository: TheAlgorithms/Java
Pull request #6274 (2025-06-08 17:02:34)

Add Boyer-Moore string search algorithm with JUnit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

PauLopNun: > Looks like a good implementation for the bad character rule!

Thanks Deniz! I don't have write permissions, so could someone with access please merge it?




Patch:
diff --git a/src/main/java/com/thealgorithms/searches/BoyerMoore.java b/src/main/java/com/thealgorithms/searches/BoyerMoore.java
new file mode 100644
index 00000000..69980215
--- /dev/null
+++ b/src/main/java/com/thealgorithms/searches/BoyerMoore.java
@@ -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);
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/searches/BoyerMooreTest.java b/src/test/java/com/thealgorithms/searches/BoyerMooreTest.java
new file mode 100644
index 00000000..9021eacb
--- /dev/null
+++ b/src/test/java/com/thealgorithms/searches/BoyerMooreTest.java
@@ -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"
+    }
+}