# 28. Implement strStr() (Easy)

https://leetcode.com/problems/implement-strstr/

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

```Input: haystack = "hello", needle = "ll"
Output: 2
```

Example 2:

```Input: haystack = "aaaaa", needle = "bba"
Output: -1
```

Clarification:

What should we return when `needle` is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when `needle` is an empty string. This is consistent to C's strstr() and Java's indexOf().

## Solutions

``````class Solution {

/*
* This problem is really frustrating with a mass of corn cases.
* Interviewers much take good care of overflow issue. To get rid of overflow,
* It's a good habit to convert all the variables to long type before calculation.
*/

public int divide(int dividend, int divisor) {
// Take care of the overflow issue
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}

if (divisor == 1) {
return dividend;
}

if (divisor == -1) {
return -dividend;
}

boolean isNegative = ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0));

// do not use below statements, Math.abs can be handle int overflow issue
// long tmpDvd = Math.abs(dividend);
// long tmpDvs = Math.abs(divisor);

long tmpDvd = dividend;
long tmpDvs = divisor;

tmpDvd = Math.abs(tmpDvd);
tmpDvs = Math.abs(tmpDvs);

int ans = 0;

long remain = tmpDvd;
while (true) {
if (remain - tmpDvs < 0) {
break;
}

int count = 0;

// 1. comparision must be >= 0, not > 0
// 2. tmpDvs must be long type, or else overflow occurs.
while (remain - (tmpDvs << count) >= 0) {
count++;
}

count--;

// to reach here, count must be >= 0

ans += (1 << count);

// Note that remain - divisor << count is absolutely different from remain - (divisor << count)
remain -= tmpDvs << count;
}

return isNegative ? -ans : ans;
}
}
``````

### 2.

``````class Solution {

// The problem should be resolved by KMP algorithm which is the most primitive way to compare strings
// against pattern.

public int strStr(String haystack, String needle) {
return kmpMatch(haystack, needle);
}

private int kmpMatch(String str, String pattern) {
if (pattern == null || pattern.length() == 0) {
return 0;
}

if (str == null || str.length() == 0) {
return -1;
}

char[] strArr = str.toCharArray();
char[] patternArr = pattern.toCharArray();

int[] next = getNextArray(patternArr);

// Pointer of the given str
int strPtr = 0;

// Pointer of the given pattern
int patternPtr = 0;

while (strPtr < strArr.length && patternPtr < patternArr.length) {
// next[0] = -1, so when patternPtr = -1, pattern differ with str at index 0
// so move both strPtr and patternPtr.
if (patternPtr == -1) {
strPtr++;

// patternPtr becomes 0
patternPtr++;
}
// Given pattern matches the given str at the head with patternPtr chars, which means
// strArr[strPtr-patternPtr:strPtr] == pattern[0:patterPtr], carry on the comparison.
else if (strArr[strPtr] == patternArr[patternPtr]) {
strPtr++;

patternPtr++;
}
// patternPtr != -1 && strArr[strPtr] != patternArr[patternPtr], pattern differ with str at certain position,
// but not the first char. Do not move forward the both pointers. Adjust the patternPtr to start a
// new comparison.
else {
// if pattern differ with str at the first char, patternPtr points to -1
patternPtr = next[patternPtr];
}
}

// all matched
if (patternPtr == patternArr.length) {
return strPtr - patternPtr;
}

return -1;
}

private int[] getNextArray(char[] pattern) {
int[] next = new int[pattern.length];

next[0] = -1;

int matchedCount;

for (int j = 1; j < pattern.length; j++) {

// suppose matchedCount = -1 or pattern[j-1] != pattern[matchedCount], next[j] should have a default value.
next[j] = 0;

// previously matched count
matchedCount = next[j - 1];
while (matchedCount != -1) {
// Standing at index j, if previous char pattern[j-1] matches the (matchedCount)th char, current next[j] increases
// And up till index j-1, next[j] chars matches

// matched chars pattern[0:matchedCount-1]
if (pattern[j - 1] == pattern[matchedCount]) {
next[j] = matchedCount + 1;

break;
}

// If not match, technically, we need to start over from the head, but we can take advantage of the previously
// computed offset information.

// !!! Important !!! You can treat substring pattern[j-matchedCount:] as the string to be matched by 'pattern',
// it will be much easier for you to understand.

// Therefore, set matchedCount to the offset that pattern failed to match substring pattern[j-matchedCount:]
// instead of a fresh start.

// Take following pattern string as example, 9th char is 'd' which differs from 5th char 'f', but we don't
// have to search from 6th char, we can take advantage of next[4]=1, then compare 1th char 'd' with 9th char 'd'.

// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] j
// [s, d, f, s, f, s, d, f, s, d, f] pattern
// [-1,0, 0, 0, 1, 0, 1, 2, 3, 4, 2] next
matchedCount = next[matchedCount];
}
}

return next;
}
}
``````