Boyer-Moore-Algorithm artificial intelligence

The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and a constant number of words of memory. It is named after Robert S. Boyer and J Strother Moore, who published it in 1981, and is a prototypical example of a streaming algorithm.

1. Technical Seminar on Boyer-Moore String Search Algorithm Kishkinda University Department of computer science & engineering Presented By : P Sahana Prasad (KUB24MCS015) HOD [ M.Tech (CSE)] Dr. Rajashree V Biradar Guided by : MR. G VannurSwamy

2. Introduction to Boyer-Moore Algorithm The Boyer-Moore algorithm is an efficient string-searching algorithm that finds a pattern within a text. It uses preprocessing techniques to skip sections of text, making it faster than simpler algorithms.

3. Steps of the Algorithm 1. **Preprocessing the Pattern:** - Create two heuristic arrays: - **Bad-character shift:** Determines the shift for mismatches. - **Good-suffix shift:** Optimizes shifts for partial matches. 2. **Pattern Matching:** - Start matching from the rightmost end of the pattern. - On mismatch, use the heuristics to decide how much to shift the pattern.

4. Bad-Character Rule For each character in the pattern, calculate how much to shift if a mismatch occurs: - For pattern **P = 'ABC'**: - 'A' → Shift by 1 (position 0) - 'B' → Shift by 2 (position 1) - 'C' → Shift by 3 (position 2) This helps skip unnecessary comparisons and speeds up the search.

5. Example Walkthrough **Text (T): ABAAABCD** **Pattern (P): ABC** 1. Start matching from the rightmost character of the pattern. 2. On mismatch, use the bad-character rule to shift the pattern. 3. Repeat until the pattern is found or the text ends.

6. Bad-Character Rule

7. Good suffix Rule

8. Summary - The Boyer-Moore algorithm is one of the fastest string-searching algorithms. - It uses two heuristics (bad-character and good-suffix) to skip sections of text. - Ideal for large texts with longer patterns. **Efficient, powerful, and widely used in real-world applications!**