🎵 String Processing Algorithms

This repository was developed to analyze and compare the efficiency of different string processing algorithms, focusing on pattern matching and text search techniques.

The project combines both theoretical analysis and practical implementation, providing detailed performance comparisons between algorithms through experimental benchmarks and mathematical analysis.

---

🧩 Implemented Algorithms

The following string matching algorithms are implemented and available for testing:

1. Brute Force
2. Knuth–Morris–Pratt (KMP)
3. Boyer–Moore–Horspool (BMH)
4. Shift–And

Each algorithm can be selected at runtime for direct comparison in execution time and matching accuracy.

---

📁 Repository Structure

/
|-- /build/    # Stores compiled object files (.o)
|-- /input/    # Input files containing text and pattern sequences
|-- /output/   # Output files with matching results and execution times
|-- /src/      # Source code files (.h and .c)
|-- /doc/      # Project documentation (doc.pdf)
|-- Makefile   # Build configuration and automation script
|-- README.md  # Project documentation and usage guide

/doc — Project Report

The /doc directory contains the document doc.pdf, which presents the complete theoretical and technical analysis of the project. The report includes:

1. Introduction

2. Code Structure and Data Handling

3. String Processing Algorithms

   • Brute Force
   • Knuth–Morris–Pratt (KMP)
   • Boyer–Moore–Horspool (BMH)
   • Shift–And

4. Result Generation and Output Files

5. Mathematical Analysis of Algorithms

6. Software Testing and Performance Comparison

7. Conclusion

8. References

---

⚙️ Compilation

To build the project, run the following command from the repository root:

make

This command compiles all source files and generates the executable tp3 in the project root.

---

🚀 Execution

Run the program with:

./sma <input-file> <algorithm>

Parameters

• <input-file> — The input file name (located in the /input/ directory). It must follow the format:

  N M
  <N musical notes separated by spaces>
  <M pattern notes separated by spaces>
  ...
  0 0
  

  Example:

  16 4
  D G A B C D G G G C D E F# G C C
  G G C D
  12 2
  C C# D D# E F F# G G# A A# B
  C D
  0 0

• <algorithm> — Specifies the search algorithm to be used:

  Value	Algorithm
  1	Brute Force
  2	Knuth–Morris–Pratt (KMP)
  3	Boyer–Moore–Horspool (BMH)
  4	Shift–And

Example

./tp3 input.txt 1

---

🧾 Output Files

The program generates its output in the /output/ directory.

1. sma.out — Matching Results

For each test case:

• S <position> → The pattern was found starting at position <position>.
• N → The pattern was not found in the text.

2. sma_benchmark.out — Performance Metrics

Contains timing information (in microseconds) for all test cases executed with the chosen algorithm. New benchmark results are appended, preserving previous data.

Example:

Algorithm CPU usage: 0.000012s
Algorithm Time spent: 0.000014s
Brute Force CPU usage: 0.000018s
Brute Force Time spent: 0.000019s
KMP CPU usage: 0.000018s
KMP Time spent: 0.000019s
BMH CPU usage: 0.000000s
BMH Time spent: 0.000014s
Shift–And CPU usage: 0.000015s
Shift–And Time spent: 0.000016s

---

🧹 Cleaning Build Files

To remove all compiled files and the executable, use:

make clean

This deletes all files in /build/ and removes the tp3 executable from the root directory.

---

💡 System Requirements

• Operating System: Linux (recommended)
• The project uses Unix-specific commands and libraries, which may require adaptation to run on Windows (e.g., changes in the Makefile and library dependencies).

---

👥 Authors

This project was developed for educational purposes as part of a course in Algorithm Analysis and Design.

Authors:

• Caio Augusto Reis
• Kariny Mylena Abrahão