Lecture 61:-  Pattern Searching

Pattern searching is a common problem in computer science where you need to find occurrences of a given pattern (substring) within a larger text (string). There are various algorithms and approaches to solve this problem, each with different time complexities and trade-offs.

One of the popular algorithms for pattern searching is the Knuth-Morris-Pratt (KMP) algorithm, which efficiently searches for occurrences of a pattern in linear time complexity O(N+M), where N is the length of the text, and M is the length of the pattern.

Here's a Java implementation of the Knuth-Morris-Pratt (KMP) algorithm for pattern searching:

javaCopy code

public class KMPAlgorithm {    public static void KMPSearch(String text, String pattern) {        int N = text.length();        int M = pattern.length();        int[] lps = computeLPSArray(pattern);        int i = 0; // index for text[]        int j = 0; // index for pattern[]        while (i < N) {            if (pattern.charAt(j) == text.charAt(i)) {                i++;                j++;            }            if (j == M) {                System.out.println("Pattern found at index " + (i - j));                j = lps[j - 1];            } else if (i < N && pattern.charAt(j) != text.charAt(i)) {                if (j != 0) {                    j = lps[j - 1];                } else {                    i++;                }            }        }    }    private static int[] computeLPSArray(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;    }    public static void main(String[] args) {        String text = "ABABDABACDABABCABAB";        String pattern = "ABABCABAB";        KMPSearch(text, pattern);    } }

In this example, the KMPSearch method implements the Knuth-Morris-Pratt algorithm to search for occurrences of the pattern in the text. The computeLPSArray method calculates the Longest Prefix which is also a Suffix (LPS) array for the given pattern.

The KMP algorithm uses the LPS array to avoid unnecessary character comparisons while searching for the pattern in the text, making it more efficient than the brute-force approach.

In the main method, we test the KMPSearch method with sample text and pattern. If the pattern is found in the text, it will print the starting index of the occurrences. In this example, the output will be:

mathematicaCopy code

Pattern found at index 10