Introduction to String Advanced

1. Basic Pattern Matching Problem

Suppose a word needs to be searched inside a larger sentence or string. The goal is to find all starting positions where the smaller pattern exactly matches a part of the text.

The useful observation is that every match must occupy a continuous block of length equal to the pattern. So the pattern can be aligned at different positions in the text and checked against the corresponding characters.

Key Points

• If the pattern length is greater than the text length, no match is possible.

• Matching is usually case-sensitive unless the problem says otherwise.

• Overlapping matches are valid in many DSA problems, such as finding "aa" in "aaaa".

Algorithm

• Check whether the pattern is empty or longer than the text, because these cases need direct handling.

• Place the pattern at each possible starting index in the text.

• Compare the pattern characters with the text characters from left to right.

• If all characters match, record the current starting index.

• Continue until every possible starting index has been checked.

• Return all recorded match positions.

Dry Run

Complexity Analysis

Time Complexity: O(n * m), where n is the text length and m is the pattern length, because each starting position may compare up to m characters.

Space Complexity: O(1), excluding the answer list, because only a few variables are needed.

2. Rabin-Karp Algorithm

Instead of comparing every character directly, a pattern can be converted into a number-like value called a hash. Each text window of the same length can also be hashed and compared with the pattern hash.

The main trick is the rolling hash. When the window moves by one position, the old hash can be updated quickly instead of recalculating the whole window from scratch.

Key Points

• Rabin-Karp is useful for multiple pattern search and plagiarism-style matching.

• Hash collisions can happen, where two different strings produce the same hash.

• A character-by-character check is still needed when hashes match.

• Average performance is fast, but poor hashing can create extra checks.

• Polynomial Rolling Hash: A polynomial rolling hash function is typically used, which treats characters like digits in a base system and updates the value in constant time as the window slides

Algorithm

• Calculate the hash value of the pattern.

• Calculate the hash value of the first text window of pattern length.

• Compare the pattern hash with the current window hash.

• If the hashes match, verify the actual characters to avoid false matches due to collision.

• Slide the window by one character and update the hash using the rolling hash idea.

• Continue until all windows are checked.

Dry Run

Complexity Analysis

Time Complexity: O(n + m) on average, because rolling hash makes each window update fast. In the worst case, collisions may cause O(n * m).

Space Complexity: O(1), excluding the answer list, because only hash values and counters are stored.

3. Prefix-Suffix Analysis

Prefix-suffix analysis focuses on identifying structural overlaps where the beginning (prefix) of a string matches its ending (suffix). Instead of scanning substrings repeatedly, this approach utilizes preprocessed prefix-suffix information—most notably the Longest Prefix Suffix (LPS) array—to solve boundary and periodicity problems efficiently.

Key Points

• A proper prefix or suffix excludes the entire string itself.

• The Longest Prefix Suffix (LPS) array stores the length of the longest proper prefix that is also a proper suffix for every prefix of the string.

• Prefix-suffix relationships help identify string symmetry, repetitions, and minimal character additions without running O(n²) comparisons.

Common Applications & Patterns

• Longest Happy Prefix: Directly computes the longest proper prefix of a string that is also a suffix using the final value of the LPS array in O(n) time.

• Shortest Palindrome: Finds the longest palindromic prefix by analyzing the prefix-suffix overlap of S + "#" + reverse(S), allowing the minimal number of characters to be prepended to make the entire string a palindrome.

Algorithm (LPS Construction)

1. Initialize an array LPS of size n with zeros and set a pointer len = 0.

2. Iterate through the string using index i from 1 to n-1.

3. If S[i] == S[len], increment len by 1, set LPS[i] = len, and move to the next index i.

4. If S[i] != S[len] and len > 0, fall back to len = LPS[len-1] without incrementing i.

5. If S[i] != S[len] and len == 0, assign LPS[i] = 0 and move to i+1.

Complexity Analysis

Time Complexity: O(n), because the pointer len increases at most n times and decreases at most n times across the entire traversal.

Space Complexity: O(n), required to store the LPS array.

4. Rolling Hash Applications

Rolling hash is used when many substrings need to be compared quickly. Instead of comparing every character again, each substring is represented by a numeric hash value.

This idea appears in problems like Repeated String Match and Repeated DNA Sequences. In these problems, the same kind of substring checking happens many times, so hashing helps reduce extra work.

Key Points

• Rolling hash converts substrings into numeric values.

• It helps compare substrings quickly.

• Hash collisions are possible, so careful checking may be needed.

• It is useful when repeated substring search is involved.

• Rolling hash applications rely on the same polynomial rolling hash method to quickly convert substrings into numeric fingerprints for fast comparisons. This idea appears in problems like Repeated String Match and Repeated DNA Sequences, where comparing strings repeatedly by characters would be too slow.

Algorithm

• Decide the fixed substring length or pattern length.

• Calculate the hash of the first substring window.

• Slide the window one character at a time.

• Update the hash by removing the old character and adding the new one.

• Track repeated hash values and confirm matches when required.

Complexity Analysis

Time Complexity: Usually O(n), because each window can be processed efficiently.

Space Complexity: O(n), when seen hash values or repeated substrings are stored.

Key Takeaways

• String Advanced is not one single algorithm. It is a collection of ideas for handling strings smarter.

• String manipulation builds comfort with words, groups, spaces, and character movement.

• Pattern matching focuses on finding one string inside another.

• Prefix-suffix problems look for useful overlap between the beginning and ending parts of a string.

• Rolling hash helps compare many substrings quickly using numeric fingerprints.

• The best way to learn this section is to understand the purpose of each technique first, then study each detailed problem separately.