String Algorithms: The Weaver of Words

The Library of Babel

Imagine a library that contains every possible combination of letters. Finding a specific sentence in that infinite chaos seems impossible. String algorithms are the librarians of this chaos. They answer two fundamental questions:

1. Search: “Does this book contain the word ‘Love’?”
2. Compression: “Can I rewrite this book using fewer pages without losing any meaning?”

In software, strings are everywhere. Source code, DNA sequences, HTTP requests, and user logs are all just strings. Mastering string algorithms means mastering the flow of information itself.

The Strategy of the Pattern

In this section, we explore the different ways to handle text:

The Three Laws of Strings

1. Prefix vs. Suffix: Most string magic happens at the edges. Knowing how a string starts (Prefix) or ends (Suffix) often tells you everything you need to know about the middle.
2. State Machines: A string algorithm is often just a robot moving through a sequence of states. “I saw an ‘H’, now I’m waiting for an ‘E’…”
3. The Alphabet Size: The complexity often depends on the alphabet ($\Sigma$). Searching binary (0/1) is different from searching Chinese text (20,000+ characters).

Summary

In this section, we will see how search engines index the web and how zip files shrink gigabytes into megabytes. We will learn that text is not just data; it is a structure waiting to be discovered.

Let’s start with the most intuitive structure of all: The Trie.