實現(xiàn) strStr() 函數(shù)。

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)。如果不存在，則返回 -1。

示例 1:

輸入: haystack = "hello", needle = "ll"
輸出: 2

示例 2:

輸入: haystack = "aaaaa", needle = "bba"
輸出: -1

說明:

當(dāng) needle 是空字符串時，我們應(yīng)當(dāng)返回什么值呢？這是一個在面試中很好的問題。

對于本題而言，當(dāng) needle 是空字符串時我們應(yīng)當(dāng)返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

方法二：雙指針 - 線性時間復(fù)雜度
上一個方法的缺陷是會將 haystack 所有長度為 L 的子串都與 needle 字符串比較，實際上是不需要這么做的。

首先，只有子串的第一個字符跟 needle 字符串第一個字符相同的時候才需要比較。

image.png

其次，可以一個字符一個字符比較，一旦不匹配了就立刻終止。

image.png

如下圖所示，比較到最后一位時發(fā)現(xiàn)不匹配，這時候開始回溯。需要注意的是，pn 指針是移動到 pn = pn - curr_len + 1 的位置，而 不是 pn = pn - curr_len 的位置。

image.png

這時候再比較一次，就找到了完整匹配的子串，直接返回子串的開始位置 pn - L。

image.png

算法

移動 pn 指針，直到 pn 所指向位置的字符與 needle 字符串第一個字符相等。

通過 pn，pL，curr_len 計算匹配長度。

如果完全匹配（即 curr_len == L），返回匹配子串的起始坐標（即 pn - L）。

如果不完全匹配，回溯。使 pn = pn - curr_len + 1， pL = 0， curr_len = 0。

復(fù)雜度分析

時間復(fù)雜度：最壞時間復(fù)雜度為 O((N - L)L)，最優(yōu)時間復(fù)雜度為 O(N)。

空間復(fù)雜度：O(1)。

public class Solution {
    public int StrStr(string haystack, string needle) {
        int l = needle.Length , n = haystack.Length;
        if(l == 0) return 0;

        int pn = 0;
        while(pn < n - l + 1){
            while(pn < n - l + 1 && needle[0] != haystack[pn]) pn++;

            int cur = 0, pl = 0;
            while(pl < l && pn < n && needle[pl] == haystack[pn]){
                pn++;
                pl++;
                cur++;
            }

            if(cur == l) return pn - l;
            pn =  pn - cur + 1; 
        }
        return -1;
    }
}