Pattern searching is a crucial problem in computer science. When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results.
A typical problem statement would be-
Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[].
Examples:
Input: txt[] = "THIS IS A TEST TEXT"
pat[] = "TExT"
Output: Pattern found at index 15
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
In this program, a text and a pattern are given as an input and a pattern is searched in the text, and we get all the instances of the pattern as an output.
Algorithm:
- Take text and pattern as input.
- Run an outer for loop from 0 to length of text-length of the pattern.
- Run an inner loop from 0 to the length of the pattern.
- Through this,, for each character at each index in the text starting from that index till index+length of pattern, the pattern is searched in the text.
- If the pattern is found, print the index of the outer loop at which that pattern is found in the text.
- Else if the pattern is not found, then print it is not found.
Below is the implementation of the above approach:
Java
// Java Program to Implement the String Search// Algorithm for Short Text Sizes import java.io.*; class GFG { public static void main(String[] args) { String text = "neveropen is a coding website for geeks"; String pattern = "geeks"; // calling the method that is designed for // printing the instances of pattern // found in the text string stringMatch(text, pattern); } public static void stringMatch(String text, String pattern) { int len_t = text.length(); int len_p = pattern.length(); int k = 0, i = 0, j = 0; // loop to find out the position Of searched pattern for (i = 0; i <= (len_t - len_p); i++) { for (j = 0; j < len_p; j++) { if (text.charAt(i + j) != pattern.charAt(j)) break; } if (j == len_p) { k++; System.out.println("Pattern Found at Position: " + i); } } if (k == 0) System.out.println("No Match Found!"); else System.out.println("Total Instances Found = " + k); }} |
Pattern Found at Position: 0 Pattern Found at Position: 8 Pattern Found at Position: 38 Total Instances Found = 3
Worst-case Time Complexity: O(m(n-m+1))
KMP algorithm is an effective way to search for a pattern inside text. While traversal when a mismatch is detected, some characters in the text of the next window are already known. Taking this advantage time complexity gets reduce to O(n).
Below is the implementation of the effective approach:
Java
// Java Program to Implement the String Search// Algorithm for Short Text Sizes class KMP_String_Matching { void KMPSearch(String pat, String txt) { int M = pat.length(); int N = txt.length(); // create lps[] that will hold the longest // prefix suffix values for pattern int lps[] = new int[M]; int j = 0; // index for pat[] // Preprocess the pattern (calculate lps[] // array) computeLPSArray(pat, M, lps); int i = 0; // index for txt[] while (i < N) { if (pat.charAt(j) == txt.charAt(i)) { j++; i++; } if (j == M) { System.out.println("Found pattern " + "at index " + (i - j)); j = lps[j - 1]; } // mismatch after j matches else if (i < N && pat.charAt(j) != txt.charAt(i)) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } } void computeLPSArray(String pat, int M, int lps[]) { // length of the previous longest prefix suffix int len = 0; int i = 1; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i < M) { if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; // Also, note that we do not increment // i here } else // if (len == 0) { lps[i] = len; i++; } } } } // Driver program to test above function public static void main(String args[]) { String text = "neveropen is a coding website for geeks"; String pattern = "geeks"; KMP_String_Matching effective = new KMP_String_Matching(); effective.KMPSearch(pattern, text); }} |
Found pattern at index 0 Found pattern at index 8 Found pattern at index 38
Time Complexity: O(n)
