标签： 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) {
        
    }
};

翻译

实现strStr()

难度系数：简单

实现strStr()。
返回匹配时的第一个索引， 如果没有匹配的就返回-1。（感觉原文用针和草堆来形容带诙谐）

思路

strstr
经典题。

假设：
遍历到的needle索引为j, haystack索引为i+j, needle,haystack长度分别为m,n

• 暴力法
  遍历haystack和needle，如果haystack[i+j] == needle[j]（匹配）， 则 j++;
  如果不等于（失配），i++, j = 0 T(O) = m * n
• KMP
  这个得专门写一篇总结的文章。
  还有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];
            }
        }
    }
};