28. Implement strStr()

问题

Implement strStr().

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

例子

yreuhudewj hud
4

分析

假设被搜索的字符串为S，要搜索的字符串为T。

• 方法一：遍历S的每一个位置，从当前位置开始匹配T。如果匹配成功，返回当前位置；如果不成功，继续遍历下一个位置。
• 方法二：kmp算法。有时间再仔细研究。

要点

brute-force即可

时间复杂度

• 方法一： O(mn)
• 方法二： O(m+n)

空间复杂度

• 方法一： O(1)
• 方法二： O(n)

代码

方法一

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

方法二

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.length(), n = needle.length();
        if (!n) return 0;
        vector<int> lps = kmpProcess(needle);
        for (int i = 0, j = 0; i < m; ) {
            if (haystack[i] == needle[j]) { 
                i++;
                j++;
            }
            if (j == n) return i - j;
            if (i < m && haystack[i] != needle[j]) {
                if (j) j = lps[j - 1];
                else i++;
            }
        }
        return -1;
    }
private:
    vector<int> kmpProcess(string& needle) {
        int n = needle.length();
        vector<int> lps(n, 0);
        for (int i = 1, len = 0; i < n; ) {
            if (needle[i] == needle[len])
                lps[i++] = ++len;
            else if (len) len = lps[len - 1];
            else lps[i++] = 0;
        }
        return lps;
    }
};