## Algorithm

Problem Name: 28. Find the Index of the First Occurrence in a String

Given two strings `needle` and `haystack`, return the index of the first occurrence of `needle` in `haystack`, or `-1` if `needle` is not part of `haystack`.

Example 1:

```Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
```

Example 2:

```Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
```

Constraints:

• `1 <= haystack.length, needle.length <= 104`
• `haystack` and `needle` consist of only lowercase English characters.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void getNext(char* pattern, int* next) {
if (pattern == NULL || next == NULL) return;

int m = strlen(pattern);
int i, j;
next[0] = 0;
j = 0;
for (i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j])
j = next[j - 1];

if (pattern[i] == pattern[j]) j++;

next[i] = j;
}
}

int strStr(char* haystack, char* needle) {
if (haystack == NULL || needle == NULL) return 0;

int n = strlen(haystack);
int m = strlen(needle);

if (m == 0) return 0;

int *next = (int *)calloc(m, sizeof(int));

getNext(needle, next);
int ans = -1;
int i, j;
j = 0;
for (i = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j])
j = next[j - 1];

if (haystack[i] == needle[j]) j++;

if (j == m) {
ans = i + 1 - j;
break;  /* if you want to continue search, comment out break */
j = next[j - 1];
}
}

free(next);
return ans;
}

/* Brute force */
int strStr0(char* haystack, char* needle) {
if (haystack == NULL || needle == NULL) return 0;

int n = strlen(haystack);
int m = strlen(needle);

if (m == 0) return 0;

int ans = -1;
int i, j;
j = 0;
for (i = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
i = i + 1 - j;
j = 0;
}

if (haystack[i] == needle[j]) j++;

if (j == m) {
ans = i + 1 - j;
break;  /* if you want to continue search, comment out break */
j = 0;
}
}

return ans;
}

int main() {
char str[] = "abcdacabcdabdeabcdabd";
char pattern[] = "abcdabd";

/* 6 */
printf("%d\n", strStr(str, pattern));

/* 0 */
printf("%d\n", strStr("", ""));

/* 0 */
printf("%d\n", strStr("1", ""));

return 0;
}

``````
Copy The Code &

Input

cmd

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.size() == 0) return 0;
for (int i = 0; i < haystack.size(); i++)
if (haystack[i] == needle[0] && isEqual(haystack.substr(i), needle)) return i;
return -1;
}

bool isEqual(string s1, string s2) {
if (s1.size() < s2.size()) return false;
for (int i = 0; i < s2.size(); i++)
if (s1[i] != s2[i]) return false;
return true;
}
};
``````
Copy The Code &

Input

cmd
haystack = "leetcode", needle = "leeto"

Output

cmd
-1

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const strStr = function(a, b) {
if(b === '') return 0
if(a.length < b.length) return -1
if(a.length === b.length) return a === b ? 0 : -1
const m = a.length, n = b.length
const fail = Array(n).fill(-1)
// DFA
for(let i = 1; i < n; i++) {
let j = fail[i - 1]
while(j !== -1 && b[j + 1] !== b[i]) {
j = fail[j]
}
if(b[j + 1] === b[i]) fail[i] = j + 1
}
let pos = -1
for(let i = 0; i < m; i++) {
while(pos !== -1 && a[i] !== b[pos + 1]) pos = fail[pos]
if(a[i] === b[pos + 1]) {
pos++
if(pos === n - 1) return i - n + 1
}
}
return -1
};
``````
Copy The Code &

Input

cmd

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def strStr(self, haystack, needle):
return haystack.find(needle)
``````
Copy The Code &

Input

cmd
haystack = "leetcode", needle = "leeto"

Output

cmd
-1

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _028_ImplementStrStr
{
public int StrStr(string haystack, string needle)
{
var needleLength = needle.Length;
if (needleLength == 0) { return 0; }

var loopLenght = haystack.Length - needleLength + 1;
var needleIndex = 0;
var n = 0;
for (int i = 0; i < loopLenght; i++)
{
needleIndex = n = 0;
while (needleIndex < needleLength
&& haystack[i + needleIndex] == needle[needleIndex])
{
if (n == 0 && needle[needleIndex] == needle[0])
{
n = needleIndex;
}
needleIndex++;
}
if (needleIndex == needleLength)
{
return i;
}
if (n > 0) i += n - 1;
}

return -1;
}
}
}
``````
Copy The Code &

Input

cmd