Sponsored
Sponsored
The brute force approach involves iterating over each possible starting position of the needle in the haystack and checking if the substring from that position matches the needle.
Time Complexity: O((m-n+1)*n), where m is the length of haystack and n is the length of needle.
Space Complexity: O(1).
1function strStr(haystack, needle) {
2 let m = haystack.length;
3 let n = needle.length;
4 if (n === 0) return 0;
5 for (let i = 0; i <= m - n; i++) {
6 let j = 0;
7 for (; j < n; j++) {
8 if (haystack[i + j] !== needle[j])
9 break;
10 }
11 if (j === n) return i;
12 }
13 return -1;
14}
15
16console.log(strStr("sadbutsad", "sad")); // Output: 0This JavaScript solution examines each substring of the haystack to check for a match with the needle.
The KMP (Knuth-Morris-Pratt) algorithm is a more efficient string-searching algorithm. It preprocesses the needle to create a longest prefix-suffix (LPS) array, which is used to skip unnecessary comparisons while searching in the haystack.
Time Complexity: O(m + n), where m is the length of haystack and n is the length of needle.
Space Complexity: O(n), due to the LPS array.
#include <vector>
using namespace std;
void computeLPSArray(string pat, int M, int* lps) {
int len = 0;
lps[0] = 0;
int i = 1;
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 strStr(string txt, string pat) {
int N = txt.size();
int M = pat.size();
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
return i - j;
j = lps[j - 1];
} else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
return -1;
}
int main() {
cout << strStr("sadbutsad", "sad") << endl; // Output: 0
return 0;
}This C++ implementation follows the KMP algorithm for efficient string searching.