---
tags: LeetCode
---

# 28. 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().

---
輸入範本如下

public class Solution {
    public int StrStr(string haystack, string needle) {
        
    }
}

### 直覺想法
一個一個比對 , 當發現子字串時候 , 回傳結果.
可以自己用迴圈一個一個比對 char , 或是使用 SubString 取出字串後再比對

72 ms	22.7 MB
You are here!
Your runtime beats 91.15 % of csharp submissions.
public int StrStr(string haystack, string needle)
{
    for (int i = 0; i < haystack.Length - needle.Length + 1; i++)
    {
        int j = 0;
        for (; j < needle.Length; j++)
        {
            if (haystack[i + j] != needle[j])
            {
                break;
            }
        }
        if (j == needle.Length)
        {
            return i;
        }
    }
    return -1;
}

76 ms	22.8 MB
You are here!
Your runtime beats 74.24 % of csharp submissions.
public int StrStr(string haystack, string needle)
{
    for (int i = 0; i < haystack.Length - needle.Length + 1; i++)
    {
        var subString = haystack.Substring(i, needle.Length);
        if (needle == subString)
        {
            return i;
        }
    }
    return -1;
}

68 ms	22.5 MB
You are here!
Your runtime beats 98.21 % of csharp submissions
// KMP 演算法
public int StrStr(string haystack, string needle)
{
    return KMP(haystack, needle);

    int KMP(string containedString, string subString)
    {
        int[] next = GetFaileFunction(subString);
        int i = 0, j = 0;
        while (i < containedString.Length && j < subString.Length)
        {
            bool condition = j == -1 || containedString[i] == subString[j];
            i = condition ? i + 1 : i;
            j = condition ? j + 1 : next[j];
        }

        return j == subString.Length ? i - j : -1;
    }

    int[] GetFaileFunction(string str)
    {
        if (str.Length <= 1)
        {
            return new int[] { -1 };
        }

        // 初始條件
        int[] FailePositions = new int[str.Length];
        int index = 0;
        int backTrackPosition = FailePositions[0] = -1; // 若 backTrackPosition 為 -1 則代表第一位即配對失敗

        // 填滿 FailePositions
        // backTrackPosition [index] 的值代表 str[0] ~ str[index-1] 的連續比對成功次數 
        while (index < str.Length - 1)
        {
            if (backTrackPosition == -1 || str[index] == str[backTrackPosition])
            {
                FailePositions[++index] = ++backTrackPosition;
            }
            else
            {
                backTrackPosition = FailePositions[backTrackPosition];
            }
        }
        return FailePositions;
    }
}

### 參考
[28. Implement strStr() 真的理解KMP](https://www.jianshu.com/p/8146e8598490)
[KMP算法的Next数组详解](https://www.cnblogs.com/tangzhengyue/p/4315393.html)
[（原创）详解KMP算法](https://www.cnblogs.com/yjiyjige/p/3263858.html)
[KMP 演算法](http://dreamisadream97.pixnet.net/blog/post/165773403-kmp-%E6%BC%94%E7%AE%97%E6%B3%95)
[12. KMP 字串匹配](https://www.junyiacademy.org/computing/algorithm/v/cG_FY1E997s)
- ababbaabababbaababbabaa , abababb

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: