String Algorithms in Java – String Matching, Pattern Searching

This blog post explores three popular string algorithms in Java: the brute force algorithm, the Knuth-Morris-Pratt algorithm, and the Rabin-Karp algorithm.

Code examples are provided for each algorithm, making it easier for developers to implement them in their own projects.

Java Data Structures & Algorithms + LEETCODE Exercises

By understanding and utilizing these algorithms, you can enhance the performance and functionality of your Java applications that involve string manipulation and searching.

Introduction TO algorithms in Java

String algorithms play a crucial role in various applications, such as text processing, data mining, and information retrieval.

In Java, there are several powerful string algorithms available for efficient string matching and pattern searching. In this blog post, we will explore some of these algorithms and provide code examples for each.

1. Brute Force Algorithm

The brute force algorithm is the simplest and most straightforward approach to string matching.

It involves comparing each character of the pattern with each character of the text until a match is found or the end of the text is reached. Although this algorithm is simple, it is not efficient for large texts or patterns.

Code Example:


public static int bruteForce(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 -1;
}

2. Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt (KMP) algorithm is an efficient string matching algorithm that avoids unnecessary character comparisons by utilizing information from previous matches.

It preprocesses the pattern to construct a partial match table, which is then used to skip comparisons when a mismatch occurs.

Code Example:


public static int kmp(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();

    int[] lps = computeLPS(pattern);

    int i = 0;
    int j = 0;
    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        }
        if (j == m) {
            return i - j;
        } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

private static int[] computeLPS(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    int len = 0;
    int i = 1;

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

3. Rabin-Karp Algorithm

The Rabin-Karp algorithm is a string matching algorithm that uses hashing to efficiently search for a pattern in a text.

It computes the hash values of the pattern and each substring of the text, and compares them to determine if there is a match.

This algorithm is particularly useful when multiple patterns need to be searched in the same text.

Code Example:


public static List rabinKarp(String text, String pattern) {
    List indices = new ArrayList<>();
    int n = text.length();
    int m = pattern.length();
    int prime = 101;
    int d = 256;
    int q = 0;
    int p = 0;
    int h = 1;

    for (int i = 0; i < m - 1; i++) {
        h = (h * d) % prime;
    }

    for (int i = 0; i < m; i++) {
        p = (d * p + pattern.charAt(i)) % prime;
        q = (d * q + text.charAt(i)) % prime;
    }

    for (int i = 0; i <= n - m; i++) {
        if (p == q) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j))
                    break;
            }
            if (j == m)
                indices.add(i);
        }
        if (i < n - m) {
            q = (d * (q - text.charAt(i) * h) + text.charAt(i + m)) % prime;
            if (q < 0)
                q = q + prime;
        }
    }
    return indices;
}

Conclusion

String algorithms are essential tools for efficient string matching and pattern searching in Java.

In this blog post, we explored three popular algorithms: the brute force algorithm, the Knuth-Morris-Pratt algorithm, and the Rabin-Karp algorithm.

Each algorithm has its own advantages and use cases, and the code examples provided can serve as a starting point for implementing these algorithms in your own projects.

By understanding and utilizing these string algorithms, you can enhance the performance and functionality of your Java applications that involve string manipulation and searching.

https://itexamsusa.blogspot.com/2023/12/mastering-matlab-programming-for.html

https://itexamsusa.blogspot.com/2023/12/monolith-vs-microservices-which-one-is.html

https://itexamsusa.blogspot.com/2023/12/publicprivate-keypairs-and-generating.html

https://itexamsusa.blogspot.com/2023/10/exam-dp-203-data-engineering-on.html

https://itexamsusa.blogspot.com/2023/10/ccnp-enterprise-advanced-routing-enarsi.html

https://itexamsusa.blogspot.com/2023/10/red-hat-certified-engineerrhce-ex294.html

https://itexamsusa.blogspot.com/2023/09/github-actions-to-auto-build-your.html

E-Hacking Tools

String Algorithms in Java – String Matching, Pattern Searching

Introduction TO algorithms in Java

1. Brute Force Algorithm

Code Example:

2. Knuth-Morris-Pratt Algorithm

Code Example:

3. Rabin-Karp Algorithm

Code Example:

Conclusion

Read More Posts

Leave a Reply Cancel reply