標(biāo)簽： C++ 算法 LeetCode 字符串 KMP

每日算法——leetcode系列

問題 Implement strStr()

Difficulty: Easy

Implement strStr().

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

class Solution {
public:
    int strStr(string haystack, string needle) {
        
    }
};

翻譯

實(shí)現(xiàn)strStr()

難度系數(shù)：簡(jiǎn)單

實(shí)現(xiàn)strStr()。
返回匹配時(shí)的第一個(gè)索引， 如果沒有匹配的就返回-1。（感覺原文用針和草堆來(lái)形容帶詼諧）

思路

strstr
經(jīng)典題。

假設(shè)：
遍歷到的needle索引為j, haystack索引為i+j, needle,haystack長(zhǎng)度分別為m,n

• 暴力法
  遍歷haystack和needle，如果haystack[i+j] == needle[j]（匹配）， 則 j++;
  如果不等于（失配），i++, j = 0 T(O) = m * n
• KMP
  這個(gè)得專門寫一篇總結(jié)的文章。
  還有Linux的grep, BM算法

代碼

class Solution {
public:
    int strStr(string haystack, string needle) {
        return strStrKMP(haystack, needle);
    }
private:
    // brute-force
    int strStrBF(string haystack, string needle) {
        
        if (needle.empty()){
            return 0;
        }
        int i = 0;
        int hSize =  (int)(haystack.size());
        int nSize = (int)(needle.size());
        if (hSize < nSize){
            return -1;
        }
        while(i < hSize){
            int j = 0;
            if (haystack[i + j] == needle[j]){
                j++;
            }else{
                i++;
                j = 0;
            }
            if (j >= nSize){
                return i;
            }
        }
        return -1;
    }
    
    // KMP
    int strStrKMP(string haystack, string needle) {
        
        if (needle.empty()){
            return 0;
        }
        int i = 0;
        int hSize = static_cast<int>(haystack.size());
        int nSize = static_cast<int>(needle.size());
        if (hSize < nSize){
            return -1;
        }
        vector<int> next(nSize, -1);
        calcNext(needle, next);
        int j = 0;
        while (i < hSize) {
            if (j == -1 || haystack[i] == needle[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
            if (j >= nSize){
                return i - nSize;
            }
        }
        return -1;
    }
    
    void calcNext(const string& needle, vector<int> &next){
        int nSize = static_cast<int>(needle.size());
        int i = 0;
        int j = -1;
        while (i < nSize - 1) {
            if (j == -1 || needle[i] == needle[j]){
                i++;
                j++;
                next[i] = j;
            }else{
                j = next[j];
            }
        }
    }
};