🔎 String Matching Algorithms: Boyer-Moore & KMP

Java implementations and algorithms of Boyer–Moore and Knuth–Morris–Pratt (KMP) string matching algorithms, created for a university assignment. Includes visual heuristics and brief, step-by-step notes.

📝 Assignment Mapping

• Part A: Concept of string matching + BM implementation with commented code.
• Part B: BM variations (e.g., Horspool) — discuss key differences & complexities (add to notes if needed).
• Part C: KMP overview + comparison with BM (time/space, strengths/weaknesses, scenarios).

📚 Overview

• Boyer–Moore (BM): Skips characters using Bad Character and Good Suffix heuristics for practical speedups.
• KMP: Uses a failure function (prefix function) to avoid re-checking matched text.

🗂 Repository Structure

algorithms/
├─ boyer-moore/
│  ├─ imgs/
│  │  ├─ badCharHeuristic.png
│  │  ├─ bmPatternMatching.png
│  │  └─ goodSuffixHeuristic.png
│  ├─ BadCharHeuristic.psu.md
│  ├─ BMPatternMatch.psu.md
│  ├─ BoyerMooreAlgo.java
│  └─ GoodSuffixHeuristic.psu.md
├─ kmp/
│  ├─ imgs/
│  │  ├─ kmpFailureFunction.png
│  │  └─ kmpPatternMatch.png
│  ├─ kmpFailureFunction.psu.md
│  └─ kmpPatternMatch.psu.md
└─ README.md

🚀 Run the Code (Java)

1. Install Latest JDK.
2. Open a terminal in the algorithm folder (e.g., algorithms/boyer-moore).
3. Compile:

   javac BoyerMooreAlgo.java

4. Run:

   java BoyerMooreAlgo

🧩 What’s Included

• Boyer-Moore with Bad Character & Good Suffix heuristics.
• KMP with Failure (LPS) table construction.
• Concise algorithms in .psu.md files.

🤝 Team Members

Special thanks to all contributors of this project.

Muhammad Ammar Danial Abdullah

Ng Xuan Hern

Low Yvonne

Lim Wei Ling

Note: This repository is for educational purposes and demonstration only.