題目描述：實現(xiàn)strStr()函數(shù)，返回子串第一次出現(xiàn)的位置，未出現(xiàn)則返回-1。如：

Input: haystack = "hello", needle = "ll"
Output: 2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

分析：暴力算法時間復(fù)雜度O(m*n)，更高效的可以用KMP、各種文本編輯器的"查找"功能大多采用的Boyer-Mooer、Rabin-Karp算法。

暴力法：即母串與子串一個字符一個字符比對，外層循環(huán)對母串遍歷haystack.size() - needle.size()遍，即子串第一個字符與母串的第幾個字符對齊，內(nèi)層循環(huán)遍歷子串各字符，看是否都與母串相應(yīng)位置字符相同。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size();
        int n = needle.size();
        int i, j;
        for (i = 0; i <= (m - n); i ++)
        {
            for (j = 0; j < n; j ++)
                if (haystack[i + j] != needle[j])
                    break;
            if (j == n)
                return i;
        }
        return -1;
    }
};

KMP法：為保證只對母串進(jìn)行一次遍歷，要記錄子串的next數(shù)組，即當(dāng)子串的某一位與母串不匹配時應(yīng)該用子串前面的哪一位來重新對應(yīng)母串的該字符。主要理解getnext函數(shù)。因為主串不回溯，next數(shù)組已提前計算，故時間復(fù)雜度O(n)。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size();
        int n = needle.size();
        if (n == 0)
            return 0;
        else if(m == 0)
            return -1;
        
        int next[n];
        getnext(needle, next);
        int i = 0, j = 0;
        while (i < m && j < n)
        {
            if (j == -1 || haystack[i] == needle[j])
            {
                i ++;
                j ++;
            }
            else
            {
                j = next[j];
            }
        }
        if (j == n) return i - n;
        else return -1;
    }
    //獲取子串的next數(shù)組，只與子串有關(guān)。對模式串needle做“自匹配”，即求出模式串前綴與后綴中重復(fù)部分，將重復(fù)信息保存在next數(shù)組中
    void getnext(string &s, int next[])
    {
        int l = s.size();
        int i = 0, j = -1;
        next[i] = -1;
        while (i < l - 1)
        {
            if (j == -1 || s[i] == s[j])
            {
                i ++; j ++;
                next[i] = j;
            }
            else
                j = next[j];
        }
    }
};

Horspool算法簡易版Boyer-Mooer算法，只實現(xiàn)了壞字符規(guī)則，沒用好后綴規(guī)則。思路見參考，第一個樣例可正確輸出2，但在樣例"mississippi" "issipi"處超時。最壞情況下時間復(fù)雜度O(m*n)

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size();
        int n = needle.size();
        if (n == 0)
            return 0;
        else if(m == 0)
            return -1;
        int i = n - 1, j = n - 1;
        while (j >= 0 && i < m)
        {
            if (haystack[i] == needle[j])
            {
                i --, j --;
            }
            else
            {
                i += dist(needle, haystack[i]);
                j = n - 1;
            }
        }
        if (j < 0) return i + 1;
        return -1;
    }
    
    int dist(string t, char c)
    {
        int l = t.length();
        int i = l - 1;
        if (t[i] == c)
            return l;
        
        i --;
        while (i >= 0)
        {
            if (t[i] == c)
                return l - 1 - i;
            else 
                i --;
        }
        return l;
    }
};

Karp-Rabin算法：這是一種一般情況下線性，最壞情況下O((n-m)*m)的算法。算法的主要思路是設(shè)計一種哈希函數(shù)，將目標(biāo)字符串映射成一個值，然后在主串中遍歷每個與目標(biāo)串長度相同的子串，用同樣的哈希函數(shù)算其值，與目標(biāo)串的哈希值相比較。相等時還要再比較此子串的每個字符與目標(biāo)串的每個字符，因為哈希函數(shù)可能有沖突。

參考

Boyer-Mooer算法講解