• Table of Contents

Substring Search Problem

Substring search is the problem of finding whether a given string (the pattern) occurs within another string (the text), and if so, at what position(s).

Figure 9.1 Substring search example.

To solve this problem, several algorithms are used, including:

• Brute-force algorithm
• Knuth-Morris-Pratt algorithm
• Boyer-Moore algorithm
• Rabin-Karp algorithm

Each algorithm will be covered in a separate section of their own.

Applications

To understand why we are interested in solving the substring search problem, it is important to note that it has a wide range of applications in various fields.

Figure 9,2 Searching for a specific word.

One of the most common applications of substring search is in text processing, where it is used to search for specific words or phrases within a larger text document.

Brute-force Algorithm

The Brute-force algorithm is a simple and straightforward algorithm for substring search. It involves iterating through the text string and comparing each character with the corresponding character in the pattern string.

Java Implementation

Here's an example implementation of the Brute-force algorithm in Java:

public static int search(String text, String pattern) {
    int N = text.length();
    int M = pattern.length();

    for (int i = 0; i <= N - M; i++) {
        int j;
        for (j = 0; j < M; j++) {
            if (text.charAt(i + j) != pattern.charAt(j)) {
                break;
            }
        }
        if (j == M) return i;
    }
    return N;
}