JavaScript Coding Test Course, String Search

Problem Description

There is a given string text and a string pattern that needs to be found.
Write a function that returns the position where pattern first appears in text.
If the pattern does not exist in text, return -1.

Input Example

• text: “hello world”
• pattern: “world”

Output Example

• Result: 6 (the string “world” starts at index 6)

Problem Solving Strategy

To solve this problem, we need to check if a specific pattern exists within the string and,
if it does, find its starting index. There are various algorithms for string searching, but
in this tutorial, we will use the most basic and intuitive method called ‘Brute Force’ and
a more efficient algorithm called ‘KMP (Knuth-Morris-Pratt)’.
Let’s first take a look at the Brute Force method.

Brute Force Approach

The Brute Force method compares all combinations of the given string and the pattern to be found.
This method is simple and easy to understand, but in the worst case, its time complexity is O(n*m),
where n is the length of the text and m is the length of the pattern.

Algorithm Steps

1. Set the variable for the length of the text (n) and the length of the pattern (m).
2. Increase the starting position of the text one by one and compare with the pattern from the current position.
3. If all character comparisons match, return the current starting index.
4. If all characters are compared and the pattern is not found, return -1.

JavaScript Code Implementation

function findFirstOccurrence(text, pattern) {
    const n = text.length;
    const m = pattern.length;

    for (let i = 0; i <= n - m; i++) {
        let j;
        for (j = 0; j < m; j++) {
            if (text[i + j] !== pattern[j]) {
                break;
            }
        }
        if (j === m) {
            return i; // Pattern found
        }
    }
    return -1; // Pattern not found
}

// Test examples
console.log(findFirstOccurrence("hello world", "world")); // 6
console.log(findFirstOccurrence("hello world", "abc")); // -1
    

KMP Algorithm

While the Brute Force method is simple, it can be inefficient. The KMP algorithm improves performance by
preventing unnecessary re-inspections during the search. The basic concept of the KMP algorithm is
‘when part of the pattern matches, reuse the remainder’.

Principle of the KMP Algorithm

The KMP algorithm optimizes string searching using a ‘partial match table (or failure function)’.
This table provides information that can be cached during the search.
The time complexity of the KMP algorithm is O(n + m), making it effective for large datasets.

Algorithm Steps

1. Create a partial match table for the pattern.
2. While comparing text and pattern, if there is a mismatch, refer to the table to specify the pattern’s position.
3. Repeat until a match is found, and ultimately return the index.

Creating the Partial Match Table

The algorithm for creating the partial match table is as follows. This table is used to adjust
the index for the next comparison based on the same prefixes and suffixes from the previously examined string.

function buildKMPTable(pattern) {
    const m = pattern.length;
    const lps = new Array(m).fill(0);
    let len = 0; 
    let i = 1;

    while (i < m) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len !== 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}
    

KMP Algorithm Code Implementation

function KMPSearch(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    const lps = buildKMPTable(pattern);
    let i = 0; // Text index
    let j = 0; // Pattern index

    while (i < n) {
        if (pattern[j] === text[i]) {
            i++;
            j++;
        }
        if (j === m) {
            return i - j; // Pattern found
        } else if (i < n && pattern[j] !== text[i]) {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1; // Pattern not found
}

// Test examples
console.log(KMPSearch("hello world", "world")); // 6
console.log(KMPSearch("hello world", "abc")); // -1
    

Conclusion

In this tutorial, we explored two algorithms for solving the string search problem,
the Brute Force method, and the KMP algorithm.
The Brute Force method is intuitive and straightforward but can be inefficient when searching large strings.
In contrast, the KMP algorithm provides a more efficient way to search for patterns.
Understanding and appropriately utilizing these diverse algorithms is important in real coding tests.

Problems related to string searching are frequently featured in coding tests, so
it’s necessary to gain experience by solving various examples.
Keep learning different algorithm problems to further enhance your skills.