02. Search Pattern (KMP Algorithm)

The problem can be found at the following link: Problem Link

✨ LeetCode Problem of the Day (POTD) Continued ✨

• As part of the LeetCode Problem of the Day (POTD) series, here is the solution for December 2, 2024. 🎯

• My latest solution is now live: 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Problem DescriptionYou are given two strings:txt: The text string in which the pattern is to be searched.pat: The pattern string to search for.The task is to print all indices in txt where pat starts, using 0-based indexing. Return an empty list if no occurrences are found.Examples:Input: txt = "abcab", pat = "ab" Output: [0, 3]Explanation: The pattern ab appears at indices 0 and 3 in the text string.Input: txt = "aaaaa", pat = "aa" Output: [0, 1, 2, 3]Input: txt = "hello", pat = "world" Output: []Constraints:1 <= txt.length, pat.length <= 10^6Both strings consist of lowercase English alphabets.My ApproachThe Knuth-Morris-Pratt (KMP) algorithm is an efficient pattern matching algorithm that avoids unnecessary comparisons, making it well-suited for this task.Compute the Longest Prefix Suffix (LPS) Array:Preprocess the pattern string pat to build the LPS array.The LPS array stores the length of the longest prefix which is also a suffix for substrings of pat.This preprocessing helps in skipping characters during comparisons.Search Using the LPS Array:Traverse the txt and use the pat LPS array to efficiently find matches.If a mismatch occurs, use the LPS array to skip unnecessary comparisons.Output the Indices:Store the starting indices of matches found in txt.Time Complexity:Preprocessing (LPS Array): O(m), where m is the length of the pattern string.Searching: O(n), where n is the length of the text string.Overall Time Complexity: O(n + m).Auxiliary Space Complexity:Space for LPS Array: O(m).Code (C)void computeLPSArray(char* pat, int m, int* lps) { int len = 0; int i = 1; lps[0] = 0; while (i < m) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } }}int* search(char pat[], char txt[], int* resultSize) { int m = strlen(pat); int n = strlen(txt); int* lps = (int*)malloc(m * sizeof(int)); if (!lps) { fprintf(stderr, "Memory allocation failed for lps\n"); exit(1); } computeLPSArray(pat, m, lps); int* result = (int*)malloc(10 * sizeof(int)); if (!result) { fprintf(stderr, "Memory allocation failed for result\n"); free(lps); exit(1); } int resCapacity = 10; int resIndex = 0; int i = 0, j = 0; while (i < n) { if (txt[i] == pat[j]) { i++; j++; } if (j == m) { if (resIndex >= resCapacity) { resCapacity *= 2; result = (int*)realloc(result, resCapacity * sizeof(int)); if (!result) { fprintf(stderr, "Memory reallocation failed for result\n"); free(lps); exit(1); } } result[resIndex++] = i - j; j = lps[j - 1]; } else if (i < n && txt[i] != pat[j]) { if (j != 0) { j = lps[j - 1]; } else { i++; } } } *resultSize = resIndex; free(lps); return result;}Code (C++)class Solution { public: vector<int> search(string& pat, string& txt) { int m = pat.size(); int n = txt.size(); vector<int> lps(m, 0); vector<int> result; int len = 0; for (int i = 1; i < m; ) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } int i = 0; int j = 0; while (i < n) { if (txt[i] == pat[j]) { i++; j++; } if (j == m) { result.push_back(i - j); j = lps[j - 1]; } else if (i < n && txt[i] != pat[j]) { if (j != 0) { j = lps[j - 1]; } else { i++; } } } return result; }};Code (Java)class Solution { private void computeLPSArray(String pat, int m, int[] lps) { int len = 0; int i = 1; while (i < m) { if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } } ArrayList<Integer> search(String pat, String txt) { ArrayList<Integer> result = new ArrayList<>(); int m = pat.length(); int n = txt.length(); int[] lps = new int[m]; computeLPSArray(pat, m, lps); int i = 0, j = 0; while (i < n) { if (txt.charAt(i) == pat.charAt(j)) { i++; j++; } if (j == m) { result.add(i - j); j = lps[j - 1]; } else if (i < n && txt.charAt(i) != pat.charAt(j)) { if (j != 0) { j = lps[j - 1]; } else { i++; } } } return result; }}Code (Python)class Solution: def computeLPSArray(self, pat, m, lps): len = 0 i = 1 while i < m: if pat[i] == pat[len]: len += 1 lps[i] = len i += 1 else: if len != 0: len = lps[len - 1] else: lps[i] = 0 i += 1 def search(self, pat, txt): result = [] m = len(pat) n = len(txt) lps = [0] * m self.computeLPSArray(pat, m, lps) i = 0 j = 0 while i < n: if txt[i] == pat[j]: i += 1 j += 1 if j == m: result.append(i - j) j = lps[j - 1] elif i < n and txt[i] != pat[j]: if j != 0: j = lps[j - 1] else: i += 1 return resultContribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count