Keywords
String Matching, KMP, Boyer-Moore, Booth, Rotation

Technologies
Python, KMP, Boyer-Moore, Booth's, Regex

This project explores the efficiency of string processing by implementing and analyzing several core algorithms in Python. It focuses on five string matching methods—including Knuth-Morris-Pratt and Boyer-Moore—alongside Booth’s algorithm for lexicographically minimal rotations. The primary objective was to validate theoretical complexity claims through experimentation, identifying how data patterns influence performance.

The results confirm the predicted linear and quadratic behaviors, highlighting the importance of intelligent preprocessing. While naive approaches struggle with larger datasets, Booth’s algorithm maintained a consistent linear bound, proving essential for circular sequence analysis. Notably, Boyer-Moore demonstrated superior speed on average inputs by skipping text, even though it shares the same theoretical complexity as KMP.

Ultimately, this study shows that while Big-O notation provides good information, the optimal algorithm choice depends on specific data distributions.