Implementstr Str Algorithm
The Implementstr Str Algorithm, also known as the strstr function, is a widely-used string matching algorithm that finds the first occurrence of a specified substring within a larger string. It returns the index position of the first character of the substring if found, otherwise, it returns -1. This algorithm is particularly useful in various applications, such as text editing, search engines, and pattern matching tasks, as it allows for efficient and precise string manipulation and analysis.
The strstr algorithm typically works by iterating through the characters of the larger string, comparing each character to the first character of the substring. If a match is found, the algorithm proceeds to compare the subsequent characters of both the substring and the main string. If all characters of the substring are found in the main string consecutively, the index of the first character is returned. If the entire main string is traversed without finding the complete substring, the algorithm returns -1. Different variations of this algorithm, such as the Knuth-Morris-Pratt or Boyer-Moore algorithm, optimize the process by reducing the number of comparisons or leveraging pre-processing techniques, resulting in improved efficiency and performance.
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int n = strlen(haystack);
int m = strlen(needle);
if (m == 0) {
return haystack;
}
vector<int> next(m, -1);
for (int i = 1, j = -1; i < m; i++) {
while (j != -1 && needle[j+1] != needle[i]) {
j = next[j];
}
if (needle[j+1] == needle[i]) {
j++;
}
next[i] = j;
}
for (int i = 0, j = -1; i < n; i++) {
while (j != -1 && needle[j+1] != haystack[i]) {
j = next[j];
}
if (needle[j+1] == haystack[i]) {
j++;
}
if (j == m - 1) {
return haystack + i - m + 1;
}
}
return NULL;
}
};
