Brute‑Force and Simple Hash‑Based Substring Search (Rabin‑Karp) Explained with Examples

The article introduces the brute‑force (BF) substring search algorithm, illustrating how it compares the pattern string with the main string character by character and returns the first matching index.

It shows step‑by‑step examples where the pattern “bce” is found in the main string “abbcefgh”, explaining each comparison round and the resulting index 2.

To improve efficiency, the article then presents a simple hash‑based sliding‑window technique (a rudimentary form of the Rabin‑Karp algorithm). It describes two hash calculation methods—character‑sum and base‑26 conversion—and adopts the character‑sum method for demonstration.

Using the same example, the article computes the hash of the pattern and successive substrings of the main string, updates the hash in O(1) time when the window slides, and finally verifies a match with a direct character comparison.

The complete Java implementation is provided, with the main search routine and helper functions for hash computation and substring comparison:

public static int rabinKarp(String str, String pattern) {
    int m = str.length();
    int n = pattern.length();
    int patternCode = hash(pattern);
    int strCode = hash(str.substring(0, n));
    for (int i = 0; i <= m - n; i++) {
        if (strCode == patternCode && compareString(i, str, pattern)) {
            return i;
        }
        if (i < m - n) {
            strCode = nextHash(str, strCode, i, n);
        }
    }
    return -1;
}
private static int hash(String s) {
    int hashcode = 0;
    for (int i = 0; i < s.length(); i++) {
        hashcode += s.charAt(i) - 'a';
    }
    return hashcode;
}
private static int nextHash(String str, int hash, int index, int n) {
    hash -= str.charAt(index) - 'a';
    hash += str.charAt(index + n) - 'a';
    return hash;
}
private static boolean compareString(int i, String str, String pattern) {
    return str.substring(i, i + pattern.length()).equals(pattern);
}

Running the program with str = "aacdesadsdfer" and pattern = "adsd" prints the first occurrence position, demonstrating the algorithm’s correctness.