leetcode筆記：Implement strStr()

leetcode筆記：Implement strStr()

一.題目描述

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

二.題目分析

實現strstr()函數。返回needle(關鍵字)在haystack(字符串)中第一次出現的位置，如果needle不在haystack中，則返回-1。由於使用暴力方法的時間復雜度為O(mn)會超時，可使用著名的KMP算法解決。該是由Knuth，Morris，Pratt共同提出的字符串匹配算法，其對於任何字符串和目標字符串，都可以在線性時間內完成匹配查找，是一個非常優秀的字符串匹配算法。

三.示例代碼

KMP算法：

class Solution {
public:
    void getNext(vector &next, string &needle) {
        int i = 0, j = -1;
        next[i] = j;
        while (i != needle.length()) {
            while (j != -1 && needle[i] != needle[j]) j = next[j];
            next[++i] = ++j;
        }
    }
    int strStr(string haystack, string needle) {
        if (haystack.empty()) return needle.empty() ? 0 : -1;
        if (needle.empty()) return 0;
        vector next(needle.length() + 1);
        getNext(next, needle);
        int i = 0, j = 0;
        while (i != haystack.length()) {
            while (j != -1 && haystack[i] != needle[j]) j = next[j];
            ++i; ++j;
            if (j == needle.length()) return i - j;
        }
        return -1;
    }
};

四.小結

對於這題，還有其他一些有名的算法，如Rabin-Karp和Boyer-Moore算法。